Scheduling parallel machines with sequence dependent set-up times in job shop industries using GA and SA

摘要

In this paper, an unprecedented and practicable job shop scheduling problem (JSSP) is presented as the fuzzy hybrid reentrant job shop and parallel machines scheduling with sequence dependent setup times. The JSSP is identified as a complicated optimisation situated in NP-hard (Non-deterministic polynomial) problems in turn. In addition, we have incorporated some applicative constraints such as: reentrant work flows, parallel machines and uncertainty as fuzzy processing times and fuzzy sequence dependent set-up times simultaneously. In a real-world job shop problem, determining exact values for the problem's factors is usually difficult, especially in human-dependent ones. Inserting uncertainty to the problem makes the job shop scheduling more practical and realistic. There is considerable work in the fuzzy job shop scheduling problem (FJSSP) but none of them has applied such complexity. A real-life work field has been studied for evaluating solving methodologies. Two distinguished metaheuristics - simulated annealing (SA) and genetic algorithm (GA) - are investigated and compared to achieve minimum of maximum fuzzy completion times (or fuzzy makespan C_(max)). The comparison results show the same performance of both proposed SA and GA in small-scale models. But in large-scale problems GA overcomes SA significantly.