Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
481221 | European Journal of Operational Research | 2010 | 13 Pages |
Abstract
The paper studies the problem of scheduling tasks on two machines to minimize the makespan. The tasks are assigned to the machine in advance. An incompatibility relation is defined over the tasks which forbids any two incompatible tasks to be processed at the same time. The problem can serve as a mathematical model for some batching problems in which the jobs are grouped in pairs on two machines. A linear-time algorithm is presented.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Irina N. Lushchakova, Vitaly A. Strusevich,