Scheduling incompatible tasks on two machines

Irina N. Lushchakova and Vitaly A. Strusevich

European Journal of Operational Research, 2010, vol. 200, issue 2, pages 334-346

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: Two; machine; scheduling; Incompatibility; graph; Max-batch; Polynomial; algorithm (search for similar items in EconPapers)
Date: 2010

Downloads: (external link)
http://www.sciencedirect.com/science/article/B6VCT ... 57b7201f0ebc32fce332
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:eee:ejores:v:200:y:2010:i:2:p:334-346

Access Statistics for this article

European Journal of Operational Research is edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Series data maintained by Heidi Boesdal ().