This paper addresses single-machine batch scheduling with job rejection and convex resource allocation. A job is either rejected, in which case a rejection penalty will be incurred, or accepted and processed on the machine. The accepted jobs are combined to form batches containing contiguously scheduled jobs. For each batch, a batch-dependent machine setup time, which is a function of the number of batches processed previously, is required before the first job in the batch is processed. Both the setup times and job processing times are controllable by allocating a continuously divisible nonrenewable resource to the jobs. The objective is to determine an accepted job sequence, a rejected job set, a partition of the accepted job sequence into batches, and resource allocation that jointly minimize a cost function based on the total delivery dates of the accepted jobs, and the job holding, resource consumption, and rejection penalties. An dynamic programming solution algorithm with running time O (n6) is developed for the problem. It is also shown that the case of the problem with a common setup time can be solved in O (n5) time.
Accepté le :
DOI : 10.1051/ro/2017040
Mots-clés : Scheduling, batching, resource allocation, rejected penalty
@article{RO_2018__52_2_315_0,
author = {Huang, Weifan and Wu, Chin-Chia and Liu, Shangchia},
title = {Single-machine batch scheduling problem with job rejection and resource dependent processing times},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {315--334},
publisher = {EDP-Sciences},
volume = {52},
number = {2},
year = {2018},
doi = {10.1051/ro/2017040},
zbl = {1401.90076},
mrnumber = {3817467},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2017040/}
}
TY - JOUR AU - Huang, Weifan AU - Wu, Chin-Chia AU - Liu, Shangchia TI - Single-machine batch scheduling problem with job rejection and resource dependent processing times JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 315 EP - 334 VL - 52 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2017040/ DO - 10.1051/ro/2017040 LA - en ID - RO_2018__52_2_315_0 ER -
%0 Journal Article %A Huang, Weifan %A Wu, Chin-Chia %A Liu, Shangchia %T Single-machine batch scheduling problem with job rejection and resource dependent processing times %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 315-334 %V 52 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2017040/ %R 10.1051/ro/2017040 %G en %F RO_2018__52_2_315_0
Huang, Weifan; Wu, Chin-Chia; Liu, Shangchia. Single-machine batch scheduling problem with job rejection and resource dependent processing times. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 315-334. doi : 10.1051/ro/2017040. http://archive.numdam.org/articles/10.1051/ro/2017040/
[1] , and , A review of scheduling research involving setup considerations. Omega 27 (1999) 219–239 | DOI
[2] , , , and , Multiprocessor scheduling with rejection. in: Seventh ACM-SIAM Symp. Discrete Algorithms (2000) 95–103 | Zbl
[3] and , Single machine batch scheduling with deadlines and resource dependent processing times. Oper. Res. Lett. 17 (1995) 243–249 | DOI | MR | Zbl
[4] , and , Single machine batch scheduling with resource dependent setup and processing times. Eur. J. Oper. Res. 135 (2001) 177–183 | DOI | MR | Zbl
[5] , and , Inequalities. Cambridge University Press, Cambridge (1934) | Zbl
[6] , , and , Convex resource allocation problems on directed acyclic graphs: Duality, complexity, special cases and extensions. Math. Oper. Res. 15 (1990) 736–748 | DOI | MR | Zbl
[7] and , Single machine scheduling with batch-dependent setup times. Inf. Proc. Lett. 98 (2006) 73–78 | DOI | MR | Zbl
[8] and , A survey of results for sequencing problems with controllable processing times. Discrete Appl. Math. 26 (1990) 271–287 | DOI | MR | Zbl
[9] and , Scheduling with batching: A review. Eur. J. Oper. Res. 120 (2000) 228–249 | DOI | MR | Zbl
[10] and , Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity. J. Oper. Res. Soc. 46 (1991) 395–406 | Zbl
[11] , The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost. Eur. J. Oper. Res. 233 (2014) 64–74 | DOI | MR | Zbl
[12] , and , A bicriteria approach to scheduling a single machine with job rejection and positional penalties.J. Comb. Optim. 23 (2012) 395–424 | DOI | MR | Zbl
[13] and , A survey of scheduling with controllable processing times. Discrete Appl. Math. 155 (2007a) 1643–1666 | DOI | MR | Zbl
[14] and , Single machine batch scheduling to minimize total completion time and resource consumption costs. J. Scheduling 10 (2007b) 255–261 | DOI | MR | Zbl
[15] , Two single-machine sequencing problems involving controllable job processing times. AIIE transactions 12 (1980a) 258–262 | DOI | MR
[16] , Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine. Oper. Res. 29 (1980b) 1155–1167. | DOI | Zbl
[17] , , and , Single-machine batch delivery scheduling with an assignable common due window. Omega 41 (2013b) 216–225 | DOI
[18] , , and , Improved algorithms for single-machine serial-batch scheduling with rejection to minimize total completion time and total tejection cost. IEEE Trans. Syst. Man Cybernetics-Systems 46 (2016) 1578–1588 | DOI
[19] , , and , Single-machine common due-date scheduling with batch delivery costs and resource-dependent processing times. Int. J. Production Res. 51 (2013a) 5083–5099 | DOI
[20] , , and , Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval. Information Sci. 274 (2014) 310–322 | DOI | MR | Zbl
Cité par Sources :
