Scheduling jobs with shared additional operations on parallel identical machines

Yakov Zinder, Joanna Berlińska*, Bertrand M.T. Lin

*此作品的通信作者

研究成果: Article同行評審

摘要

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.

原文English
文章編號106780
期刊Computers and Operations Research
170
DOIs
出版狀態Published - 10月 2024

指紋

深入研究「Scheduling jobs with shared additional operations on parallel identical machines」主題。共同形成了獨特的指紋。

引用此