Geodesic
Batch scheduling problem with due-date and fuzzy precedence relation
Kybernetika, Tome 48 (2012) no. 2, pp. 346-356 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 68Q25, 90B35, 90C29, 90C70
Keywords: single-machine; batch scheduling; modified due-date; fuzzy precedence relation; non-dominated batch sequence 
@article{KYB_2012_48_2_a12,
     author = {Li, Xuesong and Ishii, Hiroaki and Chen, Minghao},
     title = {Batch scheduling problem with due-date and fuzzy precedence relation},
     journal = {Kybernetika},
     pages = {346--356},
     year = {2012},
     volume = {48},
     number = {2},
     mrnumber = {2954331},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012_48_2_a12/}
}
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
SP  - 346
EP  - 356
VL  - 48
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/KYB_2012_48_2_a12/
LA  - en
ID  - KYB_2012_48_2_a12
ER  - 
%0 Journal Article
%A Li, Xuesong
%A Ishii, Hiroaki
%A Chen, Minghao
%T Batch scheduling problem with due-date and fuzzy precedence relation
%J Kybernetika
%D 2012
%P 346-356
%V 48
%N 2
%U http://geodesic.mathdoc.fr/item/KYB_2012_48_2_a12/
%G en
%F KYB_2012_48_2_a12
Li, Xuesong; Ishii, Hiroaki; Chen, Minghao. Batch scheduling problem with due-date and fuzzy precedence relation. Kybernetika, Tome 48 (2012) no. 2, pp. 346-356. http://geodesic.mathdoc.fr/item/KYB_2012_48_2_a12/

[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 | MR | Zbl

[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 | MR

[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 | MR | Zbl

[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 | MR | Zbl

[6] G. Dobson, U. S. Karmarkar, J. L. Rummel: Batching to minimize flow times on one machine. Management Sci. 33 (1987), 784-799. | DOI | Zbl

[7] D. S. Hochbaum, D. Landy: Scheduling with batching: Minimizing the weighted number of tardy jobs. Oper. Res. Lett. 16 (1994), 79-86. | DOI | MR | Zbl

[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

[9] G. Mosheiov, D. Oron: A single machine batch scheduling problem with bounded batch size. European J. Oper. Res. 187 (2008), 1069-1079. | DOI | MR | Zbl

[10] G. Mosheiov, D. Oron: Open-shop batch scheduling with identical jobs. European J. Oper. Res. 187 (2008), 1282-1292. | DOI | MR | Zbl

[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 | MR | Zbl

[12] D. Naddef, C. Santos: One-pass batching algorithms for the one-machine problem. Discrete Appl. Math. 21 (1988), 133-145. | DOI | MR | Zbl

[13] C. N. Pottsand, M. Y. Kovalyov: Scheduling with Batching: A review. European J. Oper. Res. 120 (2000), 228-249. | DOI | MR

[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 | Zbl

[16] D. F. Shallcross: A polynomial algorithm for a one machine batching problem. Oper. Res. Lett. 11 (1992), 213-218. | DOI | MR | Zbl

[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