The paper considers a serial-batching scheduling problem on hierarchical optimization with two regular maximum costs, where hierarchical optimization means the primary objective function is minimized, and keeping the minimum value of the primary objective function, the secondary objective function is also minimized. In serial-batching machine environment, the machine processes the jobs in batch, and the jobs in the identical batch are processed by entering into the machine together and leaving the machine together. The time taken to process a batch amounts to the total processing time of the jobs in the batch. Moreover, a fixed switching time s is inserted when a machine begins to process a new batch. We only study the unbounded model, i.e., the batch capacity is unbounded. We give an algorithm that can solve the hierarchical optimization problem in $O\left(n^{4}\right)$ time, where n denotes the number of jobs.
Cheng He, Hao Lin, Li Li
. Unbounded Serial-Batching Scheduling on Hierarchical Optimization[J]. Journal of the Operations Research Society of China, 2021
, 9(4)
: 909
-914
.
DOI: 10.1007/s40305-020-00334-5
[1] Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.:Optimization and approximation in deterministic sequencing and scheduling:a survey. Ann. Discrete Math. 5, 287-326(1979)
[2] Lawler, E.L.:Optimal sequencing of a single machine subject to precedence constraints. Manag. Sci. 19(8), 544-546(1973)
[3] Hoogeveen, H.:Multicriteria scheduling. Eur. J. Oper. Res. 167, 592-623(2005)
[4] Hoogeveen, J.A.:Single-machine scheduling to minimize a function of two or three maximum cost criteria. J. Algorithms 21, 415-433(1996)
[5] He, C., Lin, Y.X., Yuan, J.J.:Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine. Found. Comput. Decis. Sci. 33, 369-376(2008)
[6] He, C., Lin, H., Lin, Y.X.:Bounded serial-batching scheduling for minimizing maximum lateness and makespan. Discrete Optim. 16, 70-75(2015)
[7] He, C., Lin, H., Lin, Y.X., Tian, J.:Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan. Cent. Eur. J. Oper. Res. 21, 177-186(2013)
[8] Geng, Z.C., Yuan, J.J., Yuan, J.L.:Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost. Appl. Math. Comput. 332, 1-18(2018)
