Source-linked AI summary
Scheduling Jobs with Multiple Operational Modes and Tail Times
Bo Chen, Jelmer Pier van der Gaast, Xiandong Zhang
TL;DR
The paper studies how to schedule jobs when each operational mode jointly determines machine processing and a resource-free tail, requiring simultaneous mode assignment and sequencing. It formalizes this model and classifies the complexity of key objectives, showing that multiple modes make several problems hard while fixed-order cases retain tractability. The findings clarify computational limits and practical trade-offs in manufacturing systems with maturation, cooling, or curing stages.
Problem
Scheduling systems with resource-free maturation tails must choose both each job’s processing mode and the single-machine sequence, unlike traditional fixed-mode models.
Method
The paper formalizes a single-machine multi-mode scheduling model in which every mode specifies a processing time and tail time, then analyzes its objective variants and complexity.
Results
The study establishes a complexity landscape in which makespan, completion-time range, and total weighted completion time become NP-hard with two modes and strongly NP-hard with unrestricted modes, while most objectives remain polynomial for fixed sequences.
Takeaways & Limitations
The results provide theoretical limits and algorithmic possibilities for balancing synchronized completion and throughput in advanced manufacturing processes with tails.
Takeaways & Limitations
The study focuses on a single-machine bottleneck, leaving parallel-machine and flow-shop configurations for future research.
Abstract
from arXiv · showhide
This study explores a scheduling challenge inspired by the production of programmable materials, such as advanced liquid crystal displays. In these systems, the final quality of a product is reached only after a resource-free maturation period, known as a "tail", during which the machine is available for processing other jobs. Each job can be executed in one of several operational modes, with each mode determining a specific combination of machine processing time and subsequent tail duration. The primary task is to simultaneously choose the best mode for every job and determine their processing order. We analyze this model across several key performance goals, including the total time required to finish all jobs, the synchronization of completion times (the gap between the earliest and latest finished products), and the total weighted completion time. Our findings provide a detailed classification of the computational complexity of these problems. We demonstrate that while traditional versions with only one mode per job are simple to solve using standard rules, the introduction of just two modes makes finding optimal solutions for most of these goals computationally difficult. When the number of available modes is large, the complexity increases significantly. However, we also identify specific scenarios that remain efficiently solvable, such as when the processing order is already determined or when the goal is to minimize the average completion time. These results offer theoretical clarity and practical strategies for optimizing complex manufacturing and chemical processes involving forced cooling or maturation stages.
1 Introduction
The paper studies single-machine scheduling where each job’s mode jointly determines machine processing and a resource-free tail, requiring simultaneous mode selection and sequencing. It classifies the resulting problems’ complexity and identifies settings that remain tractable.
- Each job can use a mode specifying a processing time and a subsequent tail during which the machine remains available for other jobs.
- The scheduler must choose both one mode for every job and the processing order on the single machine.
- The model considers minimizing makespan, completion-time range, and total weighted completion time, as well as maximizing the minimum completion time.
- Multiple modes fundamentally increase difficulty compared with the well-understood single-mode case, although fixed job sequences permit polynomial-time mode selection for several objectives.
- The study formally defines the model and gives a complete classification distinguishing polynomially solvable, weakly NP-hard, and strongly NP-hard variants.
2 Literature review
The literature review positions this model at the intersection of scheduling with resource-free tails and scheduling with controllable processing times. Unlike prior paradigms, one discrete mode jointly determines both processing and tail durations without a separate resource cost.
- Scheduling with delivery times: Classical delivery-time scheduling assigns each job a fixed processing time and resource-free tail, with completion defined as start plus processing plus tail.
- Scheduling with delivery times: Prior work includes approximation algorithms for delivery-time models, polynomial results for several sequence-dependent-tail objectives, and an O(n log n) algorithm for discounted weighted completion time.
- Scheduling with controllable processing times: Controllable-processing-time research treats processing duration as a decision variable, typically trading shorter processing against additional resource cost.
- Scheduling with controllable processing times: Discrete controllable-processing models have also yielded polynomial formulations, including an n×n assignment reduction solvable in O(n^3) time.
- Connection to the present work: The present model fills a gap by coupling each job’s processing and tail durations through a discrete mode rather than fixing the tail, charging a separate control cost, or making the tail position-dependent.
- Connection to the present work: This coupling changes complexity: problems polynomial in the single-mode setting become NP-hard, and several become strongly NP-hard, with only two modes sometimes sufficient.
3 Problem description and preliminaries
The paper defines a single-machine scheduling model in which each job requires a mode choice and a processing order, with resource-free tails delaying completion. It establishes simple single-mode rules, polynomial solvability under fixed sequences, and broad NP-hardness when modes and sequencing interact.
- 3.1 Problem definition: Each job has multiple modes specifying machine processing and resource-free tail times, while the scheduler chooses both a job permutation and one mode per job.Completion is start time plus processing and tail time; processing is consecutive from time zero under the no-idle convention.
- 3.1 Problem definition: The model studies minimizing makespan, completion-time span Dmax, and total weighted completion time, while maximizing the minimum completion time Cmin.Idle time cannot improve minimized regular objectives but is essential for maximizing Cmin and affects Dmax complexity.
- 3.2 Preliminary lemmas for single-mode case: With two modes, Dmax is weakly NP-hard even for a fixed sequence, and Cmin is NP-hard when sequencing is also part of the decision.The summary results also report weak NP-hardness for the fixed-sequence Dmax variants, including the idle-time version.
- 3.2 Preliminary lemmas for single-mode case: When mode assignments and job sequencing are jointly chosen, Cmax, Dmax, total weighted completion time, and Cmin are strongly NP-hard.The weighted-completion objective is already NP-hard at δ = 2, while strong NP-hardness is established when δ is unrestricted.
- 3.2 Preliminary lemmas for single-mode case: With one mode per job, makespan is optimized by non-increasing tail times, weighted completion time by non-increasing wj/pj, and Cmin by non-increasing pj + qj.The weighted-completion rule runs in O(n log n), and the makespan rule is also polynomial-time solvable in O(n log n).
- 3.3 Polynomial solvability under fixed job sequence: With a fixed job sequence, mode selection is polynomially solvable for makespan, minimum completion time, and total weighted completion time.Makespan and Cmin use greedy feasibility tests with binary search, whereas weighted completion decomposes into independent job-wise mode contributions.
4 Weakly NP-hard problems
This section establishes weak NP-hardness for range minimization with a fixed sequence and for makespan and earliest-completion objectives when jobs have two modes, while fixed-sequence range minimization remains pseudo-polynomially solvable with unrestricted modes.
- 4.1 Problem 1|Mode (pij, qij), ¯π, δ = 2|Dmax: Two modes make fixed-sequence Dmax minimization NP-hard, because its simultaneous upper and lower completion-time bounds destroy the greedy monotonicity available for Cmax.A Partition reduction uses anchor and testing jobs to force the selected processing-time sum to equal B.
- 4.2 Problem 1|Mode (pij, qij), ¯π|Dmax: A fixed sequence permits a pseudo-polynomial dynamic program for Dmax even when the number of modes is part of the input.The algorithm tracks reachable cumulative-processing states within a candidate completion-time window and accepts exactly when a reachable final state exists.
- 4.3 Problem 1|Mode (pij, qij), δ = 2|Cmax: With two modes and a free sequence, minimizing Cmax is weakly NP-hard, because jointly choosing modes and positions embeds Partition in a two-block schedule.The reduction forces a makespan threshold of 3B exactly when the selected mode-1 jobs sum to B.
- 4.3 Problem 1|Mode (pij, qij), δ = 2|Dmax: The free-sequence Dmax objective is also NP-hard with two modes, via an auxiliary large-tail job that opens the schedule and transfers the Cmax hardness.The reduction makes the augmented instance’s optimal Dmax equal to the original instance’s optimal makespan.
- 4.4 Problem 1|Mode (pij, qij), δ = 2|Cmin: With two modes and a free sequence, maximizing Cmin is weakly NP-hard despite polynomial solvability in the single-mode case.An exchange argument yields an order by non-increasing pij + qij, after which a Partition construction forces the selected sum to equal B.
5 Strongly NP-hard problems
When the number of operational modes is unrestricted, all studied objectives become strongly NP-hard through reductions from 3-Partition. The proofs use mode-ordered schedules and structural properties to encode valid partitions.
- 5 Strongly NP-hard problems: Every objective studied becomes strongly NP-hard when the number of modes is unrestricted and treated as part of the input.The reductions use a number of modes that grows with the 3-Partition instance and originate from strongly NP-complete 3-Partition.
- 5.1 Problem 1|Mode (pij, qij)|Cmax: Minimizing makespan is strongly NP-hard, contrasting with weak NP-hardness when only two modes are available.The reduction from 3-Partition establishes equivalence between a partition solution and a schedule with makespan at most the target M ∗.
- 5.1 Problem 1|Mode (pij, qij)|Cmax: For makespan, jobs can be reordered by non-increasing tail within any fixed mode assignment, yielding contiguous blocks ordered by decreasing tail.This structural observation restricts the analysis to schedules processing all jobs of mode 1, then mode 2, through mode n.
- 5 Strongly NP-hard problems: Appending a single job with a large tail transfers the two-mode hardness result for completion-time range to the unrestricted-mode setting.This lifting device establishes strong NP-hardness for Dmax once the number of modes is unrestricted.
- 5.2 Problem 1|Mode (pij, qij)| P wjCj: The 3-Partition reductions force each mode block to contain exactly three jobs whose source numbers sum to B.Because B/4 < sj < B/2, two numbers sum to less than B and four sum to more than B.
- 5.3 Problem 1|Mode (pij, qij)|Cmin: Minimizing the minimum completion time is also strongly NP-hard through a polynomial reduction from 3-Partition.The construction uses ordered blocks and anchor jobs so every mode contributes a completion-time constraint, including modes with no ordinary assigned job.
6 Conclusion
The paper develops a multi-mode scheduling model with resource-free tails motivated by programmable-material printing and concrete curing. It establishes a broad complexity landscape and identifies practical implications and extensions for synchronized manufacturing.
- 6 Conclusion: The model represents jobs whose chosen mode jointly determines machine processing time and a subsequent resource-free tail.The motivating applications include blue-phase liquid crystal displays and prefabricated concrete, where quality or strength develops during maturation or curing.
- 6 Conclusion: Multiple operational modes make makespan, completion-time range, and total weighted completion time NP-hard with two modes and strongly NP-hard when modes are unrestricted.The conclusion contrasts this complexity with the often straightforward single-mode setting.
- 6 Conclusion: For completion-time range, perfect synchronization is computationally difficult even with a fixed processing order, although a pseudo-polynomial algorithm is available for practical instances.The range objective is therefore relevant to product-uniformity requirements in blue-phase liquid crystal printing.
- 6 Conclusion: Future research also includes approximation algorithms and online scheduling with real-time mode selection.These directions address near-optimal guarantees and settings where jobs arrive over time.
- 6 Conclusion: The study focuses on a single-machine bottleneck, leaving parallel-machine and flow-shop configurations for future work.These configurations are proposed to better represent complex industrial assembly lines.
- 6 Conclusion: The paper provides theoretical limits and algorithmic possibilities intended to support more efficient and synchronized advanced manufacturing processes.This conclusion is stated within the scope of multi-mode scheduling with tails.