Two-machine interval shop scheduling with time lags

We introduce and analyze the interval shop scheduling problem, where the objective is to maximize the weighted number of jobs that can be processed in a two-stage flow shop, job shop, or open shop, where each job has a fixed start and end time and requires a given transportation time, i.e., a time lag, for moving from one stage to the other. This problem is a natural extension of the parallel-machine scheduling problem with fixed start and end times, which is relatively well understood. We prove that the two-machine interval flow shop problem is {Mathematical expression}-hard in the strong sense for general time lags, even in the case of equal processing times and equal weights. The problem is solvable in polynomial time if all time lags are equal. The two-machine interval job shop problem is solvable in {Mathematical expression} time if the time lags are equal and relatively small. For the two-machine interval open shop problem, this is true as well.

• View at Publisher
• View at Scopus