Solving job-shop scheduling problems with fuzzy durations using genetic algorithms.

摘要

In reality, the processing times are often imprecise and this imprecision is critical for the scheduling procedure. This research presents a genetic algorithm approach to optimizing job shop scheduling problems, in which imprecise processing times are modeled as fuzzy numbers.; Because three-point (triangular) fuzzy numbers are used to represent imprecise processing times, the makespan will also be a three-point fuzzy number. As we know, the makespan is the longest completion time of all the jobs. The completion time of any job on any machine is equal to the starting time plus the processing time of that job on that machine. However, because the starting times and the processing times are fuzzy numbers, we use the fuzzy sum operation to compute the completion times and then we use the fuzzy max operation to compute the fuzzy makespan of a given schedule.; In this approach, the representation scheme is operation-based representation. This representation scheme guarantees that any possible permutation of the genes produces a feasible schedule.; The approach was coded in Microsoft C and tested against 33 fuzzified benchmarks. The problems are the three FT benchmarks, eleven of the La benchmarks, the five ABZ benchmarks, the ten ORB benchmarks, and the four YN benchmarks.; The robustness of the proposed GA-based scheduling system has been demonstrated. The optimal solutions for some of the crisp JSSP benchmarks have been evaluated using fuzzy processing times; the results indicate that these solutions are more sensitive to the variations in processing times than the “optimal” solutions for the fuzzy JSSPs.; A sensitivity analysis was performed to show the effect of the GA parameters, such as the size of the population, the length of the block, and the rate of mutation on the quality of solutions and computation time. This study should be very helpful to algorithm researches to tune their GA-based algorithms.; A bi-criteria optimization procedure for fuzzy JSSPs is presented. It is practically important to minimize the spread of any fuzzy makespan, as it is important to minimize the makespan itself. Experimental results have been presented for minimizing the spread criterion as well as for minimizing a linear combination criterion, which considers minimizing the fuzzy makespan and its spread. (Abstract shortened by UMI.)