Single-machine and flow-shop scheduling with supporting tasks in a nested structure

Abstract We study scheduling problems subject to supporting precedence, where each job requires a set of preparatory operations, referred to as supporting tasks. Motivated by diverse real-world applications featuring sequential and hierarchical processes, we introduce a nested structure for all supporting tasks. The objective function exclusively accounts for jobs, including total completion time and the weighted and unweighted number of late jobs. By leveraging the optimality properties unique to this structure, we develop efficient polynomial and pseudo-polynomial dynamic programming algorithms to solve single-agent problems in a single-machine setting, including an extension to the case allowing for job rejection. Then we consider two-agent problems with a constrained optimization form. These algorithms are adapted to tackle the additional complexity of the competing interests of two agents. The extension to the proportionate flow-shop problems highlights their inequivalence against counterpart problems in the single-machine setting in the presence of supporting precedence. We show that the problems are significantly more complex than their single-machine counterparts, namely that problems with due-date-based criteria are strongly $$\mathcal{N}\mathcal{P}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mi>P</mml:mi> </mml:mrow> </mml:math> -hard.