Solving Multi-Objective Fuzzy Job-Shop Scheduling Problem by a Hybrid Adaptive Differential Evolution Algorithm
Authors: Gai-Ge Wang, Da Gao, and Witold Pedrycz
Abstract:
A common scheduling problem is the job-shop scheduling problem (JSP), where multiple jobs are processed on multiple machines. Each job consists of a series of operations that must be performed in a given order, and each operation must be processed on a specific machine. The key challenge is how to arrange the operations on the machine so that the completion time is the earliest and the energy consumption is the least. The JSP is NP hard, which has very important practical significance. Because of many uncontrollable factors, such as machine delay or human factors, it is difficult to use a single real-number to express the processing and completion time of the jobs. The emergence of fuzzy sets makes the JSP become better aligned with the reality JSP with fuzzy processing time and completion time (FJSP) can model the scheduling more comprehensively, which benefits from the developments of fuzzy sets. Since there are many factors to consider in the production process, such as energy consumption and the completion time, choosing an indicator to evaluate the quality of these factors as a whole is feasible and necessary. Fuzzy relative entropy (FRE) leads to a method that can evaluate the quality of a feasible solution following the comparison between the actual value and the ideal value (multiple objectives). Therefore, the multi-objective FJSP can be transformed into a single-objective optimization problem and solved by a hybrid adaptive differential evolution (HADE) algorithm. The maximum completion time, the total delay time, and the total energy consumption of jobs will be considered. HADE adopts a mutation strategy based on DE-current-to-best. Its parameters (CR and F) are all made adaptive and normally distributed. The new individuals are selected according to the fitness value (FRE) obtained from a population consisting of N parents and N children in HADE. The algorithm is analyzed from different viewpoints, such as the convergence rate, the parameter adaptive mechanism, and the comparison with other intelligent algorithms. As the experimental results demonstrate, the performance of the HADE algorithm is better than those of some other state-of-the-art algorithms (namely, ant colony optimization, artificial bee colony, and particle swarm optimization).
