Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine

• Autorzy: He C. , Lin Y. , Yuan J.
• Języki publikacji: EN

Abstrakty

EN

This paper studies the bicriteria problem of scheduling n jobs on a serial-batching machine to minimize maximum lateness and makespan simultaneously. A serial-batching machine is a machine that can handle up to b jobs in a batch and jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the sum of the processing times of jobs in the batch. When a new batch starts, a constant setup time s occurs. We concentrate on the unbounded model, where 6 > n. We present an O(n2) algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.

Słowa kluczowe

EN

multicriteria scheduling; batching machine; maximum lateness; Pareto optimal solutions

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2008
• Tom: Vol. 33, No. 4
• Strony: 369--376
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

He C.

autor

Lin Y.

autor

Yuan J.

• Department of Mathematics, Zhengzhou University, Zhenzhou, Henan 450052, China,

Bibliografia

• [1]Agnetis A., Mirchani P.B., Pacciarelli D., Pacifici A., Scheduling problems with two competing agents, Operations Research, 52, 2004, 229-242.
• [2]Baker K.R., Smith J.C., A multiple-criterion model for machine scheduling, Journal of Scheduling, 6, 2003, 7-16.
• [3]Brucker P., Scheduling Algorithms (third edition), Springer, Berlin 2001.
• [4]Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 1979, 287-326.
• [5]He C., Lin Y.X., Yuan J.J., Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan, Theoretical Computer Science, 381, 2007, 234-240.
• [6]Hoogeveen H., Multicriteria scheduling, European Journal of Operational Research, 167, 2005, 592-623.
• [7]Hoogeveen J.A., Single-machine Scheduling to minimize a function of two or three maximum cost criteria, Journal of Algorithms, 21, 1996, 415-433.
• [8]Hoogeveen J.A., Van de Velde S.L., Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time, Operation Research Letters, 17, 1995, 205-208.
• [9]Webster S., Baker K.R., Scheduling groups of jobs on a single machine, Operations Research, 43, 1995, 692-703.