Single-machine and flow-shop scheduling with supporting tasks in a nested structure
Rui Yu et al.
What the paper says
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.
1 citation
Evidence weight
Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40
| F · citation impact | 0.16 × 0.4 = 0.06 |
| M · momentum | 0.53 × 0.15 = 0.08 |
| V · venue signal | 0.50 × 0.05 = 0.03 |
| R · text relevance † | 0.50 × 0.4 = 0.20 |
† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.