Journal of Scheduling
6 Conclusions and further research
Aloulou, M. A., Bouzaiene, A., Dridi, N., & Vanderpooten, D. (2014). A
bicriteria two-machine flow-shop serial-batching scheduling prob-
lem with bounded batch size. Journal of Scheduling, 17(1), 17–29.
Baptiste, P. (2000). Batching identical jobs. Mathematical Methods of
Operations Research, 52(3), 355–367.
Barketau, M. S., Cheng, T. C. E., Ng, C. T., Kotov, V., & Kovalyov, M.
Y. (2008). Batch scheduling of step deteriorating jobs. Journal of
Scheduling, 11(1), 17–28.
Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C.
N., Tautenhahn, T., et al. (1998). Scheduling a batching machine.
Journal of Scheduling, 1(1), 31–54.
Chandru, V., Lee, C. Y., & Uzsoy, R. (1993a). Minimizing total com-
pletion time on a batch processing machine with job families.
Operations Research Letters, 13(2), 61–65.
Chandru, V., Lee, C. Y., & Uzsoy, R. (1993b). Minimizing total com-
pletion time on batch processing machines. International Journal
of Production Research, 31(9), 2097–2121.
Cheng, T. C. E., Chen, Z. L., Kovalyov, M. Y., & Lin, B. M. T. (1996).
Parallel-machine batching and scheduling to minimize total com-
pletion time. IIE Transactions, 28(11), 953–956.
Cheng, T. C. E., & Kovalyov, M. Y. (2001). Single machine batch
schedulingwithsequentialjobprocessing. IIETransactions, 33(5),
413–420.
Coffman, E. G., Yannakakis, M., Magazine, M. J., & Santos, C. (1990).
Batch sizing and job sequencing on a single machine. Annals of
Operations Research, 26(1), 135–147.
Dang, C., & Kang, L. (2004). Batch-processing scheduling with setup
times. Journal of Combinatorial Optimization, 8(2), 137–146.
Deng, X., Feng, H., Li, G., & Liu, G. (2002). A PTAS for minimizing
total completion time of bounded batch scheduling. International
Journal of Foundations of Computer Science, 13(06), 817–827.
Gao, Y., Yuan, J. J., & Wei, Z. (2019). Unbounded parallel-batch
scheduling with drop-line tasks. Journal of Scheduling, 22(4),
449–463.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979).
Optimization and approximation in deterministic sequencing and
scheduling: A survey. Annals of Discrete Mathematics, 5, 287–
326.
He, C., Lin, H., & Lin, Y. (2015). Bounded serial-batching scheduling
for minimizing maximum lateness and makespan. Discrete Opti-
mization, 16, 70–75.
Hochbaum, D. S., & Landy, D. (1997). Scheduling semiconductor burn-
in operations to minimize total flowtime. Operations Research,
45(6), 874–885.
Ikura, Y., & Gimple, M. (1986). Efficient scheduling algorithms for
a single batch processing machine. Operations Research Letters,
5(2), 61–65.
Kovalyov, M. Y., Oulamara, A., & Soukhal, A. (2015). Two-agent
scheduling with agent specific batches on an unbounded serial
batching machine. Journal of Scheduling, 18(4), 423–434.
Lee, C. Y. (1999). Minimizing makespan on a single batch process-
ing machine with dynamic job arrivals. International Journal of
Production Research, 37(1), 219–236.
Lee, C. Y., Uzsoy, R., & Martin-Vega, L. A. (1992). Efficient algorithms
for scheduling semiconductor burn-in operations. Operations
Research, 40(4), 764–775.
Li, S. S., & Zhang, Y. Z. (2014). Serial batch scheduling on uniform
parallel machines to minimize total completion time. Information
Processing Letters, 114(12), 692–695.
In this paper, we investigate a new batch model, which is
called mixed batch, on parallel machines. The mixed batch
combines the properties of parallel batch and serial batch.
Thus, there are four kinds of batch models, i.e., parallel batch
(p-batch), serial batch (s-batch), semi-continuous batch (c-
batch) and mixed batch (m-batch). In the mixed batch model,
at most a given number of jobs can be processed in a batch
simultaneously. The processing time of a batch is a linear
function of the maximum processing time and the total pro-
cessing time of jobs in the batch. The objective is to minimize
the makespan. Theoretically, we prove that there exists an
optimal schedule in which the schedule of jobs on each
machine follows the full batch longest processing time rule.
We show that the problem on a single machine is polynomi-
ally solvable and on a fixed number of identical machines is
weakly NP-hard. Algorithmically, the full batch longest pro-
cessing time rule yields an optimal schedule for the problem
on a single machine. By analyzing and applying the optimal-
ity property of our problem, we develop a pseudopolynomial
time algorithm for the problem on a fixed number of identical
machines. We also analyze the worst-case performance ratio
of an approximation algorithm, namely Algorithm FBLPT.
Furthermore, we modify Algorithm FBLPT to improve the
worst-case performance, and prove the proposed Algorithm
LPT-Greedy performs better than Algorithm FBLPT in the
worse case.
Several topics on mixed batch scheduling deserve future
investigation. First, we note that our pseudopolynomial time
exact algorithm can be revised to constitute a fully polyno-
mial time approximation scheme (FPTAS) using appropriate
rounding techniques, such as used by Liu and Ro (2014) and
Liu et al. (2018). Second, it is valuable to further sharpen
the worst-case performance ratios of Algorithms FBLPT and
LPT-Greedy. Third, it is interesting to consider other cost
objectives, such as weighted completion time and lateness.
Fourth, it is beneficial to investigate a more general batch
setting where jobs have different sizes and the total size of
jobs in a batch cannot exceed a given capacity.
Acknowledgements We thank the Associate Editor and the two anony-
mous reviewers for their valuable comments and constructive sugges-
tions, which helpedus significantly improve the quality of our work. The
work of the first two authors was partly supported by the National Natu-
ral Science Foundation of China (Grant Nos. 51675442 and 71931007)
and the Innovation Foundation for Doctor Dissertation of Northwestern
Polytechnical University, China (Grant No. CX201808).
Liu, L., Wang, J., & Zhang, F. (2009). Scheduling jobs on parallel batch
processing machines. In ISECS International colloquium on com-
puting, communication, control, and management. CCCM 2009
(Vol. 1, pp. 78–81). IEEE.
References
Liu, L. L., Ng, C. T., & Cheng, T. C. E. (2010). On the complexity of bi-
criteria scheduling on a single batch processing machine. Journal
of scheduling, 13(6), 629–638.
Albers, S., & Brucker, P. (1993). The complexity of one-machine batch-
ing problems. Discrete Applied Mathematics, 47(2), 87–107.
123