Scheduling jobs with shared additional operations on parallel identical machines
研究将带有附加操作的作业分配到同构机器上，同一机器上共享的附加操作只需执行一次，目标是最小化完工时间。证明了问题的强NP难性，提出了混合整数线性规划和一类近似算法，并通过实验比较了性能。
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.