Article ID Journal Published Year Pages File Type
6896661 European Journal of Operational Research 2015 32 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, , ,