TY - JOUR
T1 - Scheduling jobs with shared additional operations on parallel identical machines
AU - Zinder, Yakov
AU - Berlińska, Joanna
AU - Lin, Bertrand M.T.
N1 - Publisher Copyright:
© 2024 The Author(s)
PY - 2024/10
Y1 - 2024/10
N2 - The paper is concerned with assigning jobs, each with associated additional operations, to identical machines. A machine, allocated to a job, must also process all the additional operations associated with this job. An additional operation that is associated with several jobs assigned to the same machine needs to be processed by this machine only once. The goal is to minimise the time needed for the completion of all jobs and their additional operations. It is shown that even very restricted particular cases of the considered problem remain NP-hard in the strong sense. For the general case, the paper introduces two mixed integer linear programs as well as a broad class of approximation algorithms and a performance guarantee that is valid for any algorithm in this class. It is shown that, for one of the above-mentioned NP-hard particular cases, the considered class contains the best possible approximation algorithm. The performance of the mixed integer linear programs and several approximation algorithms is compared by means of computational experiments.
AB - The paper is concerned with assigning jobs, each with associated additional operations, to identical machines. A machine, allocated to a job, must also process all the additional operations associated with this job. An additional operation that is associated with several jobs assigned to the same machine needs to be processed by this machine only once. The goal is to minimise the time needed for the completion of all jobs and their additional operations. It is shown that even very restricted particular cases of the considered problem remain NP-hard in the strong sense. For the general case, the paper introduces two mixed integer linear programs as well as a broad class of approximation algorithms and a performance guarantee that is valid for any algorithm in this class. It is shown that, for one of the above-mentioned NP-hard particular cases, the considered class contains the best possible approximation algorithm. The performance of the mixed integer linear programs and several approximation algorithms is compared by means of computational experiments.
KW - Approximation algorithms
KW - Computational complexity
KW - Duplication
KW - Parallel-machine scheduling
KW - Scheduling with communication delay
UR - http://www.scopus.com/inward/record.url?scp=85199162538&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2024.106780
DO - 10.1016/j.cor.2024.106780
M3 - Article
AN - SCOPUS:85199162538
SN - 0305-0548
VL - 170
JO - Computers and Operations Research
JF - Computers and Operations Research
M1 - 106780
ER -