Abstract
This work presents a new upper bounding approach, based on Dantzig-Wolfe decomposition and column generation, for a relatively novel problem of designing simple assembly lines to maximize their stability radius under uncertainty in task processing times. The problem considers task precedence constraints, a fixed cycle time, and a fixed number of workstations. This NP-hard optimization problem aims to assign a given set of assembly tasks to workstations in order to find the most robust feasible line configuration. The robustness of the configuration is measured by the stability radius with respect to its feasibility, i.e., the maximum increase in task processing times, for which the cycle time constraint remains satisfied. The reformulation resulting from the Dantzig-Wolfe decomposition is enhanced with valid inequalities and tight assignment intervals are used to reduce the solution space of pricing sub-problems. In addition, a bisection method is proposed as a pre-processing technique to improve the initial upper bound on the stability radius, which is an input for the pricing sub-problem. Computational experiments show that the proposed approach can significantly improve the upper bound on the stability radius for the most challenging instances.
1. Introduction
In modern manufacturing, the efficiency of an assembly line is often compromised by inherent uncertainties in task processing times. Traditional models like the Simple Assembly Line Balancing Problem (SALBP) typically assume deterministic processing times. However, variability due to human factors, machine performance, or material quality can lead to cycle time violations and significant economic losses. This paper addresses the SALBP-S variant, which seeks to maximize the stability radius—a measure of a line configuration's robustness against such uncertainties.
2. The Stability Radius Concept
The stability radius is defined as the maximum simultaneous increase in all task processing times that a specific line configuration can tolerate without exceeding the fixed cycle time. Maximizing this radius ensures that the assembly line has sufficient "breathing room" to handle delays. This problem is NP-hard, making the determination of tight upper bounds crucial for evaluating the quality of heuristic solutions and guiding exact optimization methods.
3. Methodology
The authors move beyond standard "compact" Mixed-Integer Linear Programming (MILP) models, which often struggle with large datasets, by proposing a novel framework centered on Dantzig-Wolfe (DW) decomposition and column generation.
3.1 Dantzig-Wolfe Decomposition and Valid Inequalities
The complex global problem is decomposed into a Master Problem, which coordinates task assignments across the entire line, and Pricing Sub-problems, which focus on finding feasible task sets for individual workstations. To enhance the convergence of the column generation process, the authors introduce specific valid inequalities that prune the search space by eliminating infeasible workstation configurations early.
3.2 Bisection Pre-processing
A "destructive improvement" bisection method is employed as a pre-processing step. By iteratively testing the feasibility of specific stability radius values, the algorithm establishes a significantly tighter initial upper bound, reducing the computational burden on the subsequent DW decomposition. Additionally, New Assignment Intervals (NAI) are used to refine the possible workstation assignments for each task based on single-machine scheduling theory.
4. Experimental Evaluation
The methodology was tested on a benchmark suite of 525 instances (100 tasks each) from Otto et al. (2013), categorized by Order Strength and Time Distribution. Additionally, large-scale instances with 1,000 tasks were evaluated to test the limits of the proposed bisection method.
5. Results and Discussion
- The "Peak in the Middle" Challenge: Instances where task processing times are approximately half the cycle time proved to be the most computationally difficult. These instances exhibit a high degree of combinatorial complexity, where the proposed DW approach significantly outperformed standard MILP models.
- Bound Accuracy: For the most difficult instances, the proposed Column-and-Row Generation (CFCG) approach provided upper bounds up to 70% tighter than those obtained from standard compact formulations.
- Pre-processing Efficiency: The bisection method proved remarkably efficient, improving upper bounds by an average of 23% in less than one second of CPU time. For 1,000-task instances, it reduced bounds by up to 80% in mere seconds.
6. Conclusion
This research provides a powerful new tool for calculating tight upper bounds in robust assembly line design. While the current focus is on bounding, the results lay the groundwork for a full Branch-and-Price algorithm to find optimal solutions. Future work will explore the theoretical underpinnings of the "peak in the middle" difficulty and the integration of generated columns into practical heuristic solvers for industrial applications.
Summary updated