Job-Shop Scheduling with Fuzzy Due Date by Multi-Objective Particle Swarm Optimization

چکیده مقاله

This paper addresses the challenging Fuzzy Job-Shop Scheduling Problem with Fuzzy Due Date (FJSSP-FDD), an NP-hard combinatorial optimization problem that incorporates real-world uncertainties. Unlike traditional scheduling models that assume crisp due dates, the authors consider fuzzy due dates represented as intervals, which better reflect human errors and system uncertainties. The problem is formulated with two conflicting objectives: minimizing the maximum makespan and maximizing the minimum satisfaction degree of jobs relative to their fuzzy due dates. To solve this multi-objective problem, the authors propose a modified version of the Multi-Objective Particle Swarm Optimization (MOPSO) algorithm, tailored specifically for the discrete and constrained nature of job-shop scheduling.

The main contributions of the work lie in two key enhancements to the standard MOPSO framework. First, a technical preprocessing mechanism is introduced to effectively encode the discrete scheduling solution space into a continuous representation compatible with the particle swarm optimizer. This encoding bridges the gap between the continuous nature of PSO and the discrete structure of scheduling sequences, enabling the algorithm to operate efficiently. Second, the authors implement a dynamically managed repository for storing non-dominated solutions. This repository incorporates a critical condition that periodically removes the densest 20% of solutions and replaces them with randomly generated particles, thereby preserving diversity and helping the algorithm escape local optima. The leader selection process within the repository is based on hypercube partitioning, which aids in maintaining a well-distributed Pareto front.

Experimental validation is conducted using several well-known benchmark datasets from the job-shop scheduling literature. The proposed modified MOPSO is compared against the established Non-Dominated Sorting Genetic Algorithm II (NSGA-II). Results demonstrate that the MOPSO approach consistently finds better solutions in terms of both objectives—achieving a higher minimum satisfaction degree and a lower maximum makespan across most tested instances. Furthermore, the computational efficiency of MOPSO is notable, as it requires less CPU time than NSGA-II in the majority of cases, making it a computationally effective alternative for solving FJSSP-FDD.

In conclusion, this study successfully adapts and enhances MOPSO for a previously underexplored variant of fuzzy job-shop scheduling. The integration of intelligent preprocessing and dynamic repository management proves effective in handling the problem's dual objectives and discrete constraints. The positive experimental outcomes highlight the algorithm's robustness and efficiency, offering a valuable methodological advance for scheduling under uncertainty. The authors suggest that future work could extend this approach to other fuzzy scheduling variants or integrate additional real-world constraints.