TY - JOUR
T1 - Relocation scheduling subject to fixed processing sequences
AU - Lin, Bertrand M.T.
AU - Hwang, F. J.
AU - Kononov, Alexander V.
N1 - Publisher Copyright:
© 2015, Springer Science+Business Media New York.
PY - 2016/4
Y1 - 2016/4
N2 - This study addresses a relocation scheduling problem that corresponds to resource-constrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in (Formula presented.) time, where (Formula presented.) and (Formula presented.) are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in (Formula presented.) time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NP-hard in the ordinary sense, and the case with a common job processing length is solvable in (Formula presented.) time. The studied problem for the minimization of number of tardy jobs is solvable in (Formula presented.) time. The solvability of the common-processing-time problems can be generalized to the m-machine cases, where (Formula presented.).
AB - This study addresses a relocation scheduling problem that corresponds to resource-constrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in (Formula presented.) time, where (Formula presented.) and (Formula presented.) are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in (Formula presented.) time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NP-hard in the ordinary sense, and the case with a common job processing length is solvable in (Formula presented.) time. The studied problem for the minimization of number of tardy jobs is solvable in (Formula presented.) time. The solvability of the common-processing-time problems can be generalized to the m-machine cases, where (Formula presented.).
KW - Dynamic programming
KW - Fixed sequence
KW - NP-hardness
KW - Parallel dedicated machines
KW - Relocation problem
KW - Resource-constrained scheduling
UR - http://www.scopus.com/inward/record.url?scp=84944691604&partnerID=8YFLogxK
U2 - 10.1007/s10951-015-0455-8
DO - 10.1007/s10951-015-0455-8
M3 - Article
AN - SCOPUS:84944691604
SN - 1094-6136
VL - 19
SP - 153
EP - 163
JO - Journal of Scheduling
JF - Journal of Scheduling
IS - 2
ER -