Overview
Research presented on arXiv investigates the scheduling problem within high-multiplicity flexible job shops, characterized by numerous copies of a limited set of job types requiring processing on alternative machines. The study focuses on transforming fractional machine allocations derived from fluid relaxations, which typically provide scalable workload lower bounds, into executable discrete schedules. It introduces a methodology to demonstrate that an optimal fluid allocation can be precisely achieved by a feasible, repeating discrete schedule, following a specific finite scaling process.
A key aspect of the work involves constructing such a discrete schedule. This construction entails scaling the fluid allocation to obtain integer operation counts. These operations are then placed into nonoverlapping machine intervals. The arrangement is subsequently repeated, and operations across these repetitions are linked to form individual jobs. This process ensures job precedence is maintained while preserving machine feasibility, without altering any interval placements.
For finite instances that grow in size while maintaining the same job-type composition and even with a fixed number of additional jobs, the research indicates that the gap between the optimal makespan and the fluid lower bound remains bounded by a constant. Consequently, as the instance size increases, the relative gap diminishes.
Approach
The research leverages the identified repeated structural property to develop a specific scheduling algorithm named type-based cyclic template replay (TCTR). This algorithm operates by searching for job-type templates. The search is conducted using an optimization model, critically designed such that its size remains independent of the number of job copies in the system. Once a template is selected, TCTR replays this template across the full instance.
Findings
- Optimal fluid allocations for high-multiplicity flexible job shops can be realized exactly as feasible, repeating discrete schedules, provided a suitable finite scaling is applied.
- The construction of these discrete schedules involves scaling fluid allocations to integer operation counts, positioning operations in nonoverlapping machine intervals, repeating this arrangement, and linking operations across repetitions to form individual jobs, all while maintaining machine feasibility and job precedence without interval movement.
- For growing finite instances with consistent job-type composition, even with a fixed number of extra jobs, the absolute gap between the optimal makespan and the fluid lower bound is bounded by a constant. This leads to a vanishing relative gap as the instance grows.
- The type-based cyclic template replay (TCTR) algorithm was applied to 676 multiplicity-expanded public flexible-job-shop instances.
- TCTR achieved feasibility in every tested instance.
- TCTR demonstrated a mean gap of 1.54% relative to the fluid lower bound on these instances.
- In comparison, a job-indexed adaptive large-neighborhood search achieved a 5.32% mean gap, and a hybrid genetic algorithm yielded a 6.18% mean gap on the same set of instances.