Scheduling in multi-scenario environment with an agreeable condition on job processing times

In the literature on multi-scenario scheduling problems, it is assumed that (i) each scenario defines a different possible realization of the job’s parameters; and (ii) the value of each parameter is arbitrary for any job in any scenario. Under these assumptions many multi-scenario scheduling problems have been proven to be $$\mathcal {NP}$$ NP -hard. We study a special case of this set of problems, in which there is an agreeable condition between scenarios on the processing-time parameters. Accordingly, the processing time of job $$J_{j}$$ J j under scenario $$s_{i}$$ s i is at most its value under scenario $$s_{i+1}$$ s i + 1 , for $$i=1,\ldots q-1$$ i = 1 , … q - 1 , where q is the number of different possible scenarios. We focus on three classical scheduling problems for which the single-scenario case is solvable in polynomial time, while the multi-scenario case is $$\mathcal {NP}$$ NP -hard, even when there are only two scenarios. The three scheduling problems consist of minimizing either the total completion time or the number of tardy jobs on a single machine, and minimizing the makespan in a two-machine flow-shop system. We show that the multi-scenario version of all three problems remains $$\mathcal {NP}$$ NP -hard even when processing times are agreeable and there are only two scenarios. We also show that for a more specific structure of job processing times two out of the three problems become easy to solve, while the complexity status of the third remains open for future research.