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.

► This paper studies a model of scheduling problems with constraints that some groups of jobs are processed contiguously.
► The feasibility problem is equivalent to the recognition of interval hypergraphs.
► Two polynomial-time algorithms are presented for the single machine scheduling problems with contiguity constraint to minimize the weighted total completion times and maximum lateness.