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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017040
Classification : 90B35, 90C26
Mots-clés : Scheduling, batching, resource allocation, rejected penalty
Huang, Weifan 1 ; Wu, Chin-Chia 1 ; Liu, Shangchia 1

1
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2017040/

[1] A. Allahverdi, J.N.D. Gupta and T. Aldowaisan, A review of scheduling research involving setup considerations. Omega 27 (1999) 219–239 | DOI

[2] Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall and L. Stougie, Multiprocessor scheduling with rejection. in: Seventh ACM-SIAM Symp. Discrete Algorithms (2000) 95–103 | Zbl

[3] T.C.E. Cheng and M.Y. Kovalyov, Single machine batch scheduling with deadlines and resource dependent processing times. Oper. Res. Lett. 17 (1995) 243–249 | DOI | MR | Zbl

[4] T.C.E. Cheng, A. Janiak and M.Y. Kovalyov, Single machine batch scheduling with resource dependent setup and processing times. Eur. J. Oper. Res. 135 (2001) 177–183 | DOI | MR | Zbl

[5] G.H. Hardy, J.E. Littlewood and G. Polya, Inequalities. Cambridge University Press, Cambridge (1934) | Zbl

[6] C.L. Monma, A. Schrijver, M.J. Todd and V.K. Wei, 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] G. Mosheiov and D. Oron, Single machine scheduling with batch-dependent setup times. Inf. Proc. Lett. 98 (2006) 73–78 | DOI | MR | Zbl

[8] E. Nowicki and S. Zdrzalka, A survey of results for sequencing problems with controllable processing times. Discrete Appl. Math. 26 (1990) 271–287 | DOI | MR | Zbl

[9] C.N. Potts and M.Y. Kovalyov, Scheduling with batching: A review. Eur. J. Oper. Res. 120 (2000) 228–249 | DOI | MR | Zbl

[10] C.N. Potts and L.N. Van Wassenhove, Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity. J. Oper. Res. Soc. 46 (1991) 395–406 | Zbl

[11] D. Shabtay, 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] D. Shabtay, N. Gaspar and L. Yedidsion, 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] D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times. Discrete Appl. Math. 155 (2007a) 1643–1666 | DOI | MR | Zbl

[14] D. Shabtay and G. Steiner, Single machine batch scheduling to minimize total completion time and resource consumption costs. J. Scheduling 10 (2007b) 255–261 | DOI | MR | Zbl

[15] R.G. Vickson, Two single-machine sequencing problems involving controllable job processing times. AIIE transactions 12 (1980a) 258–262 | DOI | MR

[16] R.G. Vickson, 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] Y. Yin, T.C.E. Cheng, C.-J. Hsu and C.-C. Wu, Single-machine batch delivery scheduling with an assignable common due window. Omega 41 (2013b) 216–225 | DOI

[18] Y. Yin, T.C.E. Cheng, D, Wang and C.-C. Wu, 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] Y. Yin, S.-R. Cheng, C.-C. Wu and S.-R. Cheng, 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] Y. Yin, D. Ye, and G. Zhang, 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 :