49. Makespan minimization for independent jobs with shared additional operations on parallel identical machines
Invited abstract in session TC-2: Scheduling , stream Scheduling.
Thursday, 11:30 - 13:00Room: M228
Authors (first author is the speaker)
| 1. | Joanna Berlińska
|
| Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań | |
| 2. | Yakov Zinder
|
| University of Technology Sydney | |
| 3. | Bertrand Lin
|
| Institute of Information Managementy, National Yang Ming Chiao Tung University |
Abstract
We analyze a set of independent jobs that have to be executed on parallel identical machines. Each job has a set of associated additional operations. If a machine executes a given job, it also has to 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. Our goal is to assign the jobs to the machines so as to minimize the time needed for the completion of all jobs and their additional operations. We show that even very restricted particular cases of the considered problem are strongly NP-hard. For the general case, we propose two mixed integer linear programs, as well as a broad class of polynomial-time approximation algorithms with a performance guarantee that is valid for any algorithm in this class. We show that for one of the strongly NP-hard particular cases mentioned above, the considered class contains the best possible approximation algorithm. The performance of the mixed integer linear programs and several approximation and heuristic algorithms is compared by means of computational experiments.
Keywords
- Scheduling
Status: accepted
Back to the list of papers