Journal
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
Volume 57, Issue 2, Pages 531-543Publisher
TAYLOR & FRANCIS LTD
DOI: 10.1080/00207543.2018.1456693
Keywords
scheduling; sequencing; dynamic programming; flow shop; combinatorial optimization; total late work
Categories
Funding
- Israel Science Foundation [1286/14]
Ask authors/readers for more resources
We study a scheduling problem to minimise total late work, i.e. each job is penalised according to the duration of its parts scheduled after its due-date. The machine setting is an m-machine proportionate flow shop. Two versions of the problem are studied: (i) the case that total late work refers to the last operation of the job (i.e. the operation performed on the last machine of the flow shop); (ii) the case that total late work refers to all the operations (on all machines). Both versions are known to be NP-hard. We prove a crucial property of an optimal schedule, and consequently introduce efficient pseudo-polynomial dynamic programming algorithms for the two versions. The dynamic programming algorithms are tested numerically and proved to perform well on large size instances.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available