Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9663804 | European Journal of Operational Research | 2005 | 5 Pages |
Abstract
We consider the single machine preemptive scheduling problem with some fixed jobs being previously given. The fixed jobs are already fixed in the schedule. The remaining jobs are to be assigned to the remaining time-slots of machine in such a way that they do not overlap each other and do not overlap with the fixed jobs. The objective is to minimize a tardiness related criterion. If the jobs are processed without preemption, it has been implied in the literature that this problem is strongly NP-hard. Suppose now that the jobs are processed preemptively, and that some specified free jobs must be on-time under the schedule. The considered problem will be denoted by 1|FB,pmtn,Ron-time|F, where F is a tardiness related criterion. We show that the considered problem is polynomially equivalent to the problem 1|FB,pmtn|F. We also show that 1|FB,pmtn|âwjUj is polynomially equivalent to 1â¥âwjUj. Consequently, the complexity of the problem 1|FB,pmtn,Ron-time|F is classified according to different choices of F.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Jinjiang Yuan, Yixun Lin,