Skipping strategy (SS) for initial population of job-shop scheduling problem

Abstract

This paper introduces a novel Skipping Strategy (SS) designed specifically to generate high-quality initial populations for meta-heuristic algorithms tackling the Job-Shop Scheduling Problem (JSSP). The authors emphasize that the initial population is a critical factor influencing both the convergence speed and the final solution quality of computationally demanding optimization techniques. The proposed strategy moves beyond simple random initialization by employing a structured, rule-based approach that leverages the problem's inherent constraints to construct promising starting points.

The core methodological contribution lies in the conceptual framework of "Plates-Jobs" and "mPlates-Jobs." The process begins by determining the Sequence of Jobs on Machines (SJM) from a given problem instance. The operations are then systematically classified into "Plates-Jobs," which group jobs based on the machine required for a specific operation step. These are subsequently reorganized into "mPlates-Jobs," which consolidate all jobs destined for the same machine across different operation steps. This reorganization provides a clear, machine-centric view of the scheduling constraints. A set of four specific rules is then formulated to govern the manipulation of jobs within and between these mPlates, focusing on merging consecutive operations, aligning jobs with their designated plates, sorting by processing time, and managing job candidates across plates.

The Skipping Strategy itself is the algorithmic procedure that applies these rules to a candidate SJM. It involves a step-by-step process of matching the current processing order of jobs on each machine with their predefined "real" order in the mPlates structure. By selectively moving and swapping jobs only when specific feasibility conditions—related to completion times and processing sequences—are satisfied, the strategy iteratively refines the schedule. This method effectively "skips" poor configurations and directly constructs active schedules that are both feasible and of higher quality than those generated by purely random methods.

The effectiveness of the SS is validated through experiments on well-known JSSP benchmark datasets, including Ft, La, and Abz series. The key positive outcome is demonstrated by the Relative Percentage Error (RPE) metric, which measures the deviation of the best solution in the initial population from the Best-Known Solution (BKS). The SS achieved notably low average RPEs, such as 3.6% for the Ft datasets and 4.3% for the La datasets. A particularly significant result was achieved for the Willem dataset, where the SS generated an initial point that was 2.1% better than the previously known BKS, indicating its powerful exploration capability. These results show that the SS can consistently produce initial populations very close to, and sometimes even surpassing, high-quality reference solutions, thereby providing a superior starting point for subsequent meta-heuristic search processes.

In conclusion, this work presents a sophisticated and effective initialization technique that addresses a fundamental challenge in solving JSSPs. By intelligently structuring the solution space via mPlates-Jobs and applying a rule-based skipping strategy, the method successfully generates dense, high-quality initial populations. This advancement can significantly reduce the computational burden on the main optimization algorithm by starting the search from a promising region, ultimately leading to faster convergence and better final schedules. The positive experimental comparisons underscore the practical value of this approach for enhancing the performance of population-based meta-heuristics in complex scheduling domains.