Electromagnetic-Like Mechanism for Job-Shop Scheduling by Novel Heuristic Initialization

چکیده مقاله

This paper proposes an advanced hybrid approach to tackle the Fuzzy Job-Shop Scheduling Problem (JSSP) with flexible due dates by integrating a novel heuristic initialization method with an improved metaheuristic optimizer. The core problem is based on Xie's model, where each job has a fuzzy due date represented as an interval, and the objective is to maximize the minimum satisfaction degree of jobs, reflecting a decision-maker's preference for completion times within the acceptable window. To solve this complex discrete optimization problem, the authors develop a two-part methodology: a sophisticated heuristic initialization technique called RDOSS and an enhanced version of the Electromagnetic-like Mechanism (IEM).

A significant contribution of this work is the introduction of the RDOSS (Reduce the Distance of Operations from the Sources and the Sinks) heuristic. This intelligent initialization strategy moves beyond simple random generation by leveraging the structural properties of the schedule. It conceptualizes "source" and "sink" operations—the first and last jobs processed on each machine—and analyzes the paths between them. By identifying and strategically modifying the longest paths that create delays, RDOSS directly constructs high-quality initial schedules that are close to optimal solutions. This is crucial because, as the authors emphasize, a high-quality starting population dramatically accelerates the convergence of subsequent metaheuristic search processes.

To optimize these initial solutions, the paper presents an Improved Electromagnetic-like Mechanism (IEM). Recognizing that the standard EM is designed for continuous problems, the authors implement key adaptations for the discrete JSSP. This includes a dual encoding scheme that translates schedules between a machine-based representation for initialization and an operation-based representation with random keys for the continuous EM operations. Furthermore, the IEM incorporates an intelligent local search (ILS) guided by the "second-generation rules" of mPlates-Jobs, which provides a structured neighborhood to explore efficiently. A notable innovation is the "multi-memorized movement" procedure, where particles remember a fraction of their previous force, allowing for more nuanced and controlled exploration of the search space compared to memoryless approaches.

The experimental validation demonstrates the effectiveness of the combined RDOSS and IEM approach across a wide range of 15 benchmark datasets, including both classic and fuzzy JSSP instances. The results show that initialization with RDOSS (and other proposed heuristics like ISS-FGR and ISS-SGR) consistently leads to better final solution quality and significantly faster convergence times compared to standard random initialization when used with the GEM (General EM) algorithm. More importantly, the standalone IEM algorithm, even with random initialization, outperforms the GEM, finding better solutions with higher convergence speeds and smoother performance curves. A key achievement is the establishment of new lower bounds (improved best-known solutions) for several benchmark instances, such as the Willem dataset.

In conclusion, this research makes a substantial contribution by addressing two critical aspects of metaheuristic application to JSSPs: intelligent initialization and algorithm enhancement. The RDOSS heuristic provides a powerful method to generate superior starting points, while the IEM's adaptations—including intelligent local search and force memorization—create a more effective and efficient optimizer. The synergistic combination of these components offers a robust and high-performing framework for solving fuzzy JSSPs with flexible due dates, effectively bridging the gap between the problem's discrete nature and the requirements of continuous population-based optimizers. The positive results underscore the importance of tailored preprocessing and initialization strategies in achieving state-of-the-art scheduling solutions.