A Robust Intelligent Construction Procedure for Job-Shop Scheduling

چکیده مقاله

This paper by Abdolrazzagh-Nezhad and Abdullah introduces a novel and intelligent initialization technique designed to generate high-quality initial populations for population-based meta-heuristic algorithms solving the Job-Shop Scheduling Problem (JSSP). Recognizing that the quality of the initial population significantly impacts the convergence speed and final solution quality of algorithms like Genetic Algorithms or Particle Swarm Optimization, the authors address a common shortcoming: the prevalent use of simple random initialization, which often produces points far from the optimal region and requires extensive computational time for refinement.

The core innovation of this work is the "Robust Intelligent Construction Procedure," which is built upon a new heuristic framework. The key mechanism is an Intelligent Skipping Strategy (ISS) that guides the search from a primal schedule to an improved one. This strategy is empowered by a novel classification of jobs called "mPlates-Jobs." This classification organizes jobs based on the predetermined sequence of operations (SOJ) and the structure of the schedule encoding (SJM), effectively capturing the problem's constraints. To activate and guide this classification, the authors propose a set of "Activator Rules" (ARs) that define probabilistic ranges for the processing order of jobs on each machine, thereby intelligently reducing the vast solution space.

The proposed procedure operates in a structured manner. It begins by generating a primal schedule using a simple priority rule. Then, iteratively, it selects a machine at random and applies the ISS-ARs to modify the order of jobs on that machine and its related machines, aiming to find a better schedule. The process incorporates control parameters to manage the search depth and avoid stagnation, ensuring diversity in the generated population. A significant advantage highlighted is the method's flexibility to produce an initial population of any specified size while maintaining proximity to optimal solutions.

The experimental validation demonstrates the substantial achievements of this technique. When tested on standard benchmark datasets from the OR-library, the ISS-ARs procedure consistently generated initial populations containing points very close to, and in several cases matching, the Best-Known Solutions (BKS). Notably, for instances like La01, La02, and La03, the BKS was actually found within the initial population itself. Furthermore, for the Willem dataset, the method generated a point that surpassed the previously known best solution. In comparative analyses, the quality of the best point in the initial population produced by ISS-ARs was superior to those generated by classic methods like the Giffler & Thompson algorithm, various simulated priority rules, and other state-of-the-art initialization heuristics proposed by Kuczapski et al. and Yahyaoui et al. Importantly, these high-quality results were achieved within a relatively short and acceptable computational time.

In conclusion, the primary achievement of this paper is the development of a fast, intelligent, and robust heuristic that serves a dual purpose: it is an effective standalone method for generating high-quality schedules and a powerful preprocessing tool to enhance any population-based meta-heuristic for JSSP. By systematically producing initial points near the optimal region, it addresses a critical bottleneck in meta-heuristic applications, potentially leading to faster convergence and better final solutions. The work establishes a strong foundation for future research to refine the procedure further and adapt its core ideas to other complex scheduling problems beyond the classical JSSP.