TL;DR
This paper tackles the complex problem of scheduling jobs on multiple machines to minimize both early and late completion penalties. The authors introduce new, more effective lower bounds by extending existing methods and exploring time-indexed formulations, significantly improving the ability to solve these challenging scheduling problems.
What Problem Does This Paper Address?
The "earliness-tardiness scheduling problem" is a real-world challenge where companies want to finish jobs as close to their due dates as possible. Finishing too early incurs storage costs, while finishing too late incurs penalty costs. While this problem has been studied extensively for a single machine, extending it to multiple identical machines (the "parallel machine environment") with distinct due dates for each job introduces significant complexity. Existing methods for parallel machines often struggle to provide tight lower bounds, which are crucial for developing efficient algorithms to find optimal or near-optimal schedules. This paper aims to bridge this gap by developing and comparing new, stronger lower bounds for this NP-hard problem.
Methods
The paper proposes two main families of lower bounds:
- Assignment-based lower bounds: These are generalizations of methods developed for the single-machine case. They reframe the problem as an assignment problem, where jobs are assigned to time slots. The authors adapt and extend these to the parallel machine setting.
- Time-indexed formulation-based lower bounds: This approach uses a detailed mathematical model where time is discretized into small periods. The authors explore two key strategies:
- Linear Relaxation with Column Generation: They start with a large mathematical model and iteratively add relevant "columns" (variables) to improve the lower bound. This is a standard technique for large-scale optimization problems.
- Lagrangean Relaxation: This involves relaxing certain constraints of the time-indexed formulation and introducing "Lagrangean multipliers" to penalize these relaxations. The authors explore two specific relaxations: one that allows jobs to be processed multiple times (relaxing the "occurrence" constraint) and another that relaxes the machine capacity constraints.
Additionally, a simple local search heuristic is presented to generate upper bounds, which are then used to evaluate the quality of the lower bounds.
Datasets
The authors generated a set of instances for their computational experiments. These instances were created using parameters commonly found in the earliness-tardiness scheduling literature. Key parameters varied include:
- Number of jobs ($n \in \{30, 60, 90\}$)
- Number of machines ($m \in \{1, 2, 4, 6\}$)
- Tardiness factor ($\tau \in \{0.2, 0.5, 0.8\}$)
- Range parameter ($\rho \in \{0.2, 0.5, 0.8\}$)
They also tested their algorithms on instances from the "Masc Lib" library, which are derived from real-world manufacturing scheduling problems.
Key Insights and Ideas
- Generalizing single-machine bounds is effective: The paper demonstrates that extending successful single-machine lower bounding techniques to the parallel machine environment can yield significant improvements.
- Time-indexed formulations are powerful but computationally demanding: While these formulations provide strong lower bounds, their sheer size can be a bottleneck. Techniques like column generation and Lagrangean relaxation are essential to make them tractable.
- Lagrangean relaxation of resource constraints is particularly promising: The authors found that relaxing the machine capacity constraints in the time-indexed formulation yielded the best lower bounds in their experiments, offering a good balance between tightness and computational efficiency.
- A small gap between upper and lower bounds is achievable: The experimental results show that the gap between the best lower bound found and the heuristic upper bound is remarkably small (around 1.5%), suggesting that the problem is well-understood and solvable in practice.
Key Results
- The proposed lower bounds, particularly the Lagrangean relaxation of resource constraints (LAGRES), significantly outperform previous methods in terms of tightness.
- The gap between the best lower bound and the heuristic upper bound was consistently small, around 1.5% on average.
- The local search heuristic (HEUR) was found to be very efficient, finding good solutions in seconds.
- For parallel machines ($m > 1$), the time-indexed formulation-based lower bounds (LINCG, LAGRES, LAGOCC) generally provided tighter bounds than assignment-based methods (AssSKS, AssBKY), although assignment-based methods could be faster for the single-machine case.
- The computational cost of algorithms generally increased with the number of jobs and decreased with the number of machines (except for LAGOCC).
Limitations and Future Work
- Computational time for column generation: While LINCG provides strong bounds, it can be time-consuming, especially for larger instances. The authors suggest that improving the subgradient method or developing heuristics for finding good Lagrangean multipliers could be beneficial for branch-and-bound procedures.
- "Sink generation" for assignment-based bounds: For the assignment-based lower bounds, the authors found that an iterative approach to determine the flow network size ("sink generation") was more efficient than using the full theoretical horizon.
- Future work: The authors suggest that an efficient branch-and-bound procedure could be derived from their best lower bound (LAGRES). They also note that further improvements to the subgradient method and heuristics for finding good Lagrangean multipliers would be valuable.
Summary updated