Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
single-machine; batch scheduling; modified due-date; fuzzy precedence relation; non-dominated batch sequence
single-machine; batch scheduling; modified due-date; fuzzy precedence relation; non-dominated batch sequence
Summary:
A single-machine batch scheduling problem is investigated. Each job has a positive processing time and due-date. Setup times are assumed to be identical for all batches. All batch sizes cannot exceed a common upper bound. As in many practical situations, jobs have to be subject to flexible precedence constraints. The aim of this paper is to find an optimal batch sequence. The sequence is to minimize the maximal completion time and maximize the minimum value of desirability of the fuzzy precedence. However, there usually exists no batch sequence optimizing both objectives at a time. Therefore, we seek some non-dominated batch sequences after the definition of non-dominated batch sequence. Based on an iterative Procedure HL proposed by Cheng et al., an efficient algorithm is presented to find some non-dominated batch sequences.
References:
[1] P. Brucker: Scheduling Algorithm. Springer-Verlag, Berlin 2006.
[2] P. Brucker, A. Gladky, H. Hoogeveen, M. Y. Kovalyov, C. N. Potts, T. Tautenhahn, S. V. Velde: Scheduling a batching machine. J. Scheduling 1 (1998), 31-54. DOI 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R | MR 1642261 | Zbl 0909.90172
[3] T. C. E. Cheng, A. Janiak: Single machine batch scheduling with deadline and resource dependent processing times. Oper. Res. Lett. 17 (1995), 243-249. DOI 10.1016/0167-6377(95)00011-8 | MR 1357082
[4] T. C. E. Cheng, A. Janiak, M. Y. Kovalyov: Single machine batch scheduling with resource dependent setup and processing times. European J. Oper. Res. 135 (2001), 177-183. DOI 10.1016/S0377-2217(00)00312-X | MR 1853962 | Zbl 1077.90525
[5] E. G. Coffman Jr., M. Yannakakis, M. J. Magazine, C. Santos: Batch sizing and job sequencing on a single machine. Ann. Oper. Res. 26 (1990), 135-147. DOI 10.1007/BF02248589 | MR 1087820 | Zbl 0712.90035
[6] G. Dobson, U. S. Karmarkar, J. L. Rummel: Batching to minimize flow times on one machine. Management Sci. 33 (1987), 784-799. DOI 10.1287/mnsc.33.6.784 | Zbl 0624.90047
[7] D. S. Hochbaum, D. Landy: Scheduling with batching: Minimizing the weighted number of tardy jobs. Oper. Res. Lett. 16 (1994), 79-86. DOI 10.1016/0167-6377(94)90063-9 | MR 1301747 | Zbl 0820.90052
[8] E. L. Lawler, J. M. Moore: A functional equation and its application to resource allocation and scheduling problems. Management Sci. 16 (1969), 77-84. DOI 10.1287/mnsc.16.1.77
[9] G. Mosheiov, D. Oron: A single machine batch scheduling problem with bounded batch size. European J. Oper. Res. 187 (2008), 1069-1079. DOI 10.1016/j.ejor.2006.01.052 | MR 2378330 | Zbl 1137.90510
[10] G. Mosheiov, D. Oron: Open-shop batch scheduling with identical jobs. European J. Oper. Res. 187 (2008), 1282-1292. DOI 10.1016/j.ejor.2006.03.068 | MR 2378339 | Zbl 1137.90511
[11] G. Mosheiov, D. Oron, Y. Ritov: Minimizing flow-time on a single machine with integer batch sizes. Oper. Res. Lett. 33 (2005), 497-501. DOI 10.1016/j.orl.2004.09.007 | MR 2146614 | Zbl 1195.90043
[12] D. Naddef, C. Santos: One-pass batching algorithms for the one-machine problem. Discrete Appl. Math. 21 (1988), 133-145. DOI 10.1016/0166-218X(88)90049-2 | MR 0959425 | Zbl 0661.90044
[13] C. N. Pottsand, M. Y. Kovalyov: Scheduling with Batching: A review. European J. Oper. Res. 120 (2000), 228-249. DOI 10.1016/S0377-2217(99)00153-8 | MR 1785709
[14] C. N. Pottsand, L. N. Van Wasenhove: Interacting scheduling with batching and lot sizing: a review of algorithm and complexity. J. Oper. Res. Soc. 43 (1992), 395-406.
[15] C. Santos, M. Magazine: Batching in single operation manufacturing systems. Oper. Res. Lett. 4 (1985), 338-343. DOI 10.1016/0167-6377(85)90011-2 | Zbl 0572.90051
[16] D. F. Shallcross: A polynomial algorithm for a one machine batching problem. Oper. Res. Lett. 11 (1992), 213-218. DOI 10.1016/0167-6377(92)90027-Z | MR 1183669 | Zbl 0760.90059
[17] C. S. Sung, U. G. Joo: Batching to minimize weighted mean flow time on a single machine with batch size restrictions. Comput. and Industr. Engrg. 32 (1997), 333-340. DOI 10.1016/S0360-8352(96)00300-2
Search
Partner of
