Scheduling incompatible tasks on two machines

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.

MoreLess

Year of publication:	2010
Authors:	Lushchakova, Irina N. ; Strusevich, Vitaly A.
Published in:	European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 200.2010, 2, p. 334-346
Publisher:	Elsevier
Keywords:	Two machine scheduling Incompatibility graph Max-batch Polynomial algorithm

Online Resource

Check full text access |

More access options

Check Google Scholar

In libraries world-wide (WorldCat)

In German libraries (KVK)

subito order

I need help

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005023403