Scheduling incompatible tasks on two machines
Tools
Tools
Tools
Lushchakova, Irina N. and Strusevich, Vitaly A. (2010) Scheduling incompatible tasks on two machines. European Journal of Operational Research, 200 (2). pp. 334-346.
Full text not available from this repository.Official URL: http://dx.doi.org/10.1016/j.ejor.2009.01.029
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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | two machine scheduling, incompatibility graph, max-batch, polynomial algorithm |
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science T Technology > T Technology (General) |
| School / Department / Research Groups: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences |
| Related URLs: | |
| Last Modified: | 08 Jan 2013 15:23 |
| URI: | http://gala.gre.ac.uk/id/eprint/4240 |
Actions (login required)
| View Item |