Batch scheduling problem with due-date and fuzzy precedence relation

Xuesong Li; Hiroaki Ishii; Minghao Chen

Kybernetika (2012)

  • Volume: 48, Issue: 2, page 346-356
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Li, Xuesong, Ishii, Hiroaki, and Chen, Minghao. "Batch scheduling problem with due-date and fuzzy precedence relation." Kybernetika 48.2 (2012): 346-356. <http://eudml.org/doc/247149>.

@article{Li2012,
abstract = {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.},
author = {Li, Xuesong, Ishii, Hiroaki, Chen, Minghao},
journal = {Kybernetika},
keywords = {single-machine; batch scheduling; modified due-date; fuzzy precedence relation; non-dominated batch sequence},
language = {eng},
number = {2},
pages = {346-356},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Batch scheduling problem with due-date and fuzzy precedence relation},
url = {http://eudml.org/doc/247149},
volume = {48},
year = {2012},
}

TY - JOUR
AU - Li, Xuesong
AU - Ishii, Hiroaki
AU - Chen, Minghao
TI - Batch scheduling problem with due-date and fuzzy precedence relation
JO - Kybernetika
PY - 2012
PB - Institute of Information Theory and Automation AS CR
VL - 48
IS - 2
SP - 346
EP - 356
AB - 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.
LA - eng
KW - single-machine; batch scheduling; modified due-date; fuzzy precedence relation; non-dominated batch sequence
UR - http://eudml.org/doc/247149
ER -

References

top
  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, 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R, J. Scheduling 1 (1998), 31-54. Zbl0909.90172MR1642261DOI10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R
  3. T. C. E. Cheng, A. Janiak, 10.1016/0167-6377(95)00011-8, Oper. Res. Lett. 17 (1995), 243-249. MR1357082DOI10.1016/0167-6377(95)00011-8
  4. T. C. E. Cheng, A. Janiak, M. Y. Kovalyov, 10.1016/S0377-2217(00)00312-X, European J. Oper. Res. 135 (2001), 177-183. Zbl1077.90525MR1853962DOI10.1016/S0377-2217(00)00312-X
  5. E. G. Coffman Jr., M. Yannakakis, M. J. Magazine, C. Santos, 10.1007/BF02248589, Ann. Oper. Res. 26 (1990), 135-147. Zbl0712.90035MR1087820DOI10.1007/BF02248589
  6. G. Dobson, U. S. Karmarkar, J. L. Rummel, 10.1287/mnsc.33.6.784, Management Sci. 33 (1987), 784-799. Zbl0624.90047DOI10.1287/mnsc.33.6.784
  7. D. S. Hochbaum, D. Landy, 10.1016/0167-6377(94)90063-9, Oper. Res. Lett. 16 (1994), 79-86. Zbl0820.90052MR1301747DOI10.1016/0167-6377(94)90063-9
  8. E. L. Lawler, J. M. Moore, 10.1287/mnsc.16.1.77, Management Sci. 16 (1969), 77-84. DOI10.1287/mnsc.16.1.77
  9. G. Mosheiov, D. Oron, 10.1016/j.ejor.2006.01.052, European J. Oper. Res. 187 (2008), 1069-1079. Zbl1137.90510MR2378330DOI10.1016/j.ejor.2006.01.052
  10. G. Mosheiov, D. Oron, 10.1016/j.ejor.2006.03.068, European J. Oper. Res. 187 (2008), 1282-1292. Zbl1137.90511MR2378339DOI10.1016/j.ejor.2006.03.068
  11. G. Mosheiov, D. Oron, Y. Ritov, 10.1016/j.orl.2004.09.007, Oper. Res. Lett. 33 (2005), 497-501. Zbl1195.90043MR2146614DOI10.1016/j.orl.2004.09.007
  12. D. Naddef, C. Santos, 10.1016/0166-218X(88)90049-2, Discrete Appl. Math. 21 (1988), 133-145. Zbl0661.90044MR0959425DOI10.1016/0166-218X(88)90049-2
  13. C. N. Pottsand, M. Y. Kovalyov, 10.1016/S0377-2217(99)00153-8, European J. Oper. Res. 120 (2000), 228-249. MR1785709DOI10.1016/S0377-2217(99)00153-8
  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, 10.1016/0167-6377(85)90011-2, Oper. Res. Lett. 4 (1985), 338-343. Zbl0572.90051DOI10.1016/0167-6377(85)90011-2
  16. D. F. Shallcross, 10.1016/0167-6377(92)90027-Z, Oper. Res. Lett. 11 (1992), 213-218. Zbl0760.90059MR1183669DOI10.1016/0167-6377(92)90027-Z
  17. C. S. Sung, U. G. Joo, 10.1016/S0360-8352(96)00300-2, Comput. and Industr. Engrg. 32 (1997), 333-340. DOI10.1016/S0360-8352(96)00300-2

NotesEmbed ?

top

You must be logged in to post comments.