[go: up one dir, main page]

Kybernetika 48 no. 2, 346-356, 2012

Batch scheduling problem with due-date and fuzzy precedence relation

Xuesong Li, Hiroaki Ishii and Minghao Chen

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.

Keywords:

single-machine, batch scheduling, modified due-date, fuzzy precedence relation, non-dominated batch sequence

Classification:

90B35, 90C29, 90C70, 68Q25

paper.pdf

References:

  1. P. Brucker: Scheduling Algorithm. Springer-Verlag, Berlin 2006.   CrossRef
  2. P. Brucker, A. Gladky, H. Hoogeveen, M. Y. Kovalyov, C. N. Potts, T. Tautenhahn and S. V. Velde: Scheduling a batching machine. J. Scheduling 1 (1998), 31-54.   CrossRef
  3. T. C. E. Cheng and A. Janiak: Single machine batch scheduling with deadline and resource dependent processing times. Oper. Res. Lett. 17 (1995), 243-249.   CrossRef
  4. T. C. E. Cheng, A. Janiak and M. Y. Kovalyov: Single machine batch scheduling with resource dependent setup and processing times. European J. Oper. Res. 135 (2001), 177-183.   CrossRef
  5. E. G. Coffman Jr., M. Yannakakis, M. J. Magazine and C. Santos: Batch sizing and job sequencing on a single machine. Ann. Oper. Res. 26 (1990), 135-147.   CrossRef
  6. G. Dobson, U. S. Karmarkar and J. L. Rummel: Batching to minimize flow times on one machine. Management Sci. 33 (1987), 784-799.   CrossRef
  7. D. S. Hochbaum and D. Landy: Scheduling with batching: Minimizing the weighted number of tardy jobs. Oper. Res. Lett. 16 (1994), 79-86.   CrossRef
  8. E. L. Lawler and J. M. Moore: A functional equation and its application to resource allocation and scheduling problems. Management Sci. 16 (1969), 77-84.   CrossRef
  9. G. Mosheiov and D. Oron: A single machine batch scheduling problem with bounded batch size. European J. Oper. Res. 187 (2008), 1069-1079.   CrossRef
  10. G. Mosheiov and D. Oron: Open-shop batch scheduling with identical jobs. European J. Oper. Res. 187 (2008), 1282-1292.   CrossRef
  11. G. Mosheiov, D. Oron and Y. Ritov: Minimizing flow-time on a single machine with integer batch sizes. Oper. Res. Lett. 33 (2005), 497-501.   CrossRef
  12. D. Naddef and C. Santos: One-pass batching algorithms for the one-machine problem. Discrete Appl. Math. 21 (1988), 133-145.   CrossRef
  13. C. N. Pottsand and M. Y. Kovalyov: Scheduling with Batching: A review. European J. Oper. Res. 120 (2000), 228-249.   CrossRef
  14. C. N. Pottsand and 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.   CrossRef
  15. C. Santos and M. Magazine: Batching in single operation manufacturing systems. Oper. Res. Lett. 4 (1985), 338-343.   CrossRef
  16. D. F. Shallcross: A polynomial algorithm for a one machine batching problem. Oper. Res. Lett. 11 (1992), 213-218.   CrossRef
  17. C. S. Sung and 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.   CrossRef