Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6896661 | European Journal of Operational Research | 2015 | 32 Pages |
Abstract
We study various two-agent scheduling problems on a single machine with equal job processing times. The equal processing time assumption enables us to design new polynomial-time or faster-than-known optimization algorithms for many problems. We prove, however, that there exists a subset of problems for which the computational complexity remains NP-hard. The set of hard problems includes different variations where the objective functions of the two agents are either minimizing the weighted sum of completion times or the weighted number of tardy jobs. For these problems, we present pseudo-polynomial time algorithms.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Daniel Oron, Dvir Shabtay, George Steiner,