| Title:
|
Batch scheduling problem with due-date and fuzzy precedence relation (English) |
| Author:
|
Li, Xuesong |
| Author:
|
Ishii, Hiroaki |
| Author:
|
Chen, Minghao |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
48 |
| Issue:
|
2 |
| Year:
|
2012 |
| Pages:
|
346-356 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
single-machine |
| Keyword:
|
batch scheduling |
| Keyword:
|
modified due-date |
| Keyword:
|
fuzzy precedence relation |
| Keyword:
|
non-dominated batch sequence |
| MSC:
|
68Q25 |
| MSC:
|
90B35 |
| MSC:
|
90C29 |
| MSC:
|
90C70 |
| idMR:
|
MR2954331 |
| . |
| Date available:
|
2012-05-15T16:23:26Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/142819 |
| . |
| Reference:
|
[1] P. Brucker: Scheduling Algorithm..Springer-Verlag, Berlin 2006. |
| Reference:
|
[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. Zbl 0909.90172, MR 1642261, 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R |
| Reference:
|
[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. MR 1357082, 10.1016/0167-6377(95)00011-8 |
| Reference:
|
[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. Zbl 1077.90525, MR 1853962, 10.1016/S0377-2217(00)00312-X |
| Reference:
|
[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. Zbl 0712.90035, MR 1087820, 10.1007/BF02248589 |
| Reference:
|
[6] G. Dobson, U. S. Karmarkar, J. L. Rummel: Batching to minimize flow times on one machine..Management Sci. 33 (1987), 784-799. Zbl 0624.90047, 10.1287/mnsc.33.6.784 |
| Reference:
|
[7] D. S. Hochbaum, D. Landy: Scheduling with batching: Minimizing the weighted number of tardy jobs..Oper. Res. Lett. 16 (1994), 79-86. Zbl 0820.90052, MR 1301747, 10.1016/0167-6377(94)90063-9 |
| Reference:
|
[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. 10.1287/mnsc.16.1.77 |
| Reference:
|
[9] G. Mosheiov, D. Oron: A single machine batch scheduling problem with bounded batch size..European J. Oper. Res. 187 (2008), 1069-1079. Zbl 1137.90510, MR 2378330, 10.1016/j.ejor.2006.01.052 |
| Reference:
|
[10] G. Mosheiov, D. Oron: Open-shop batch scheduling with identical jobs..European J. Oper. Res. 187 (2008), 1282-1292. Zbl 1137.90511, MR 2378339, 10.1016/j.ejor.2006.03.068 |
| Reference:
|
[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. Zbl 1195.90043, MR 2146614, 10.1016/j.orl.2004.09.007 |
| Reference:
|
[12] D. Naddef, C. Santos: One-pass batching algorithms for the one-machine problem..Discrete Appl. Math. 21 (1988), 133-145. Zbl 0661.90044, MR 0959425, 10.1016/0166-218X(88)90049-2 |
| Reference:
|
[13] C. N. Pottsand, M. Y. Kovalyov: Scheduling with Batching: A review..European J. Oper. Res. 120 (2000), 228-249. MR 1785709, 10.1016/S0377-2217(99)00153-8 |
| Reference:
|
[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. |
| Reference:
|
[15] C. Santos, M. Magazine: Batching in single operation manufacturing systems..Oper. Res. Lett. 4 (1985), 338-343. Zbl 0572.90051, 10.1016/0167-6377(85)90011-2 |
| Reference:
|
[16] D. F. Shallcross: A polynomial algorithm for a one machine batching problem..Oper. Res. Lett. 11 (1992), 213-218. Zbl 0760.90059, MR 1183669, 10.1016/0167-6377(92)90027-Z |
| Reference:
|
[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. 10.1016/S0360-8352(96)00300-2 |
| . |
