Robust start for population-based algorithms solving job-shop scheduling problems

چکیده مقاله

The paper titled “Robust Start for Population-Based Algorithms Solving Job-Shop Scheduling Problems,” presented at the 2011 Conference on Data Mining and Optimization, introduces a novel initialization approach for population-based algorithms applied to the job-shop scheduling problem (JSSP). The authors, Majid Abdolrazzagh-Nezhad and Salwani Abdullah, argue that generating a high-quality initial population is crucial for reducing the time to reach optimal or near-optimal solutions in JSSP, which is known as an NP-complete combinatorial optimization problem. Traditional methods often rely on random initialization or simple priority rules, which may not ensure good distribution or proximity to optimal solutions. In response, the authors propose a structured method that first maps each schedule to a unique Sequence of Jobs on Machines (SJM) matrix, then introduces the new concept of “job plates” to categorize and constrain job sequences based on operation order.

The core contribution of the work lies in three new initialization procedures that leverage the SJM representation along with refined concepts of head and tail paths—originally used in insertion techniques—to evaluate and improve schedules. These procedures systematically adjust job orders on machines by considering gaps in the schedule and applying rules derived from the job plates framework. The improvement strategies include shifting job orders based on the shortest head and tail paths, designing a switching function that identifies and fills gaps in the schedule, and using priority rules such as earliest processing time, earliest completion time, and earliest due date to generate initial SJM matrices. This structured initialization aims to produce schedules that are not only active but also closer to the optimal makespan.

The proposed methods were tested on 73 benchmark instances from the OR-library, including well-known datasets such as FT, LA, ORB, ABZ, SWV, and YN. The results demonstrate significant improvements over existing initialization techniques, including priority dispatching rules, the Giffler–Thompson algorithm, and other heuristic approaches. Notably, the method labeled M&S3 consistently outperformed others in both solution quality and computational efficiency. In several instances, the initial population generated by the proposed procedures already contained the best-known solution, underscoring the effectiveness of the approach. Additionally, the computational times remained acceptable, making the method practical for real-world applications.

In summary, this paper makes a valuable contribution to the field of job-shop scheduling by offering a systematic and effective initialization strategy for population-based algorithms. The introduction of job plates and the refined use of SJM matrices provide a structured way to generate high-quality starting points, which can accelerate convergence and improve the final scheduling outcomes. The experimental validation across a wide range of benchmarks confirms the robustness and superiority of the proposed methods, suggesting their potential for integration into various metaheuristic frameworks for scheduling and optimization.