Machine scheduling with contiguous processing constraints
In classical machine scheduling problems the jobs are independent in general. Motivated by some special processing environments, this paper studies a model of scheduling problems with constraints that some groups of jobs have to be processed contiguously. It turns out that the feasibility of these constrained scheduling problems is equivalent to the recognition of interval hypergraphs. For this new model, two examples of single machine scheduling problems with polynomial-time algorithms are taken as a start. (c) 2013 Elsevier B.V. All rights reserved.
scheduling contiguous processing feasibility polynomial-time algorithm optimality