Voir la notice de l'article provenant de la source Numdam
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.
Huang, Weifan 1 ; Wu, Chin-Chia 1 ; Liu, Shangchia 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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
Cité par Sources :