An effective immune algorithm based on novel dispatching rules for the flexible flow-shop scheduling problem with multiprocessor tasks

摘要

As a strongly NP-hard problem, the flexible flow-shop problem with multiprocessor tasks (FFSPMT) has gained much attention due to its academic significance and wide application background. To solve the FFSPMT, the dispatching rule is crucial to decode job order sequences to schedules, which has a great effect on the quality of the solution. In this paper, several novel dispatching rules are proposed to arrange the job processing order and machine assignment to minimize makespan of the FFSPMT by narrowing the idle time between the consecutive operations in the processor as well as by increasing the flexibility in selecting processors to schedule the following operations. With these rules, an immune algorithm (IA) is proposed to solve the FFSPMT, where special crossover, mutation, and vaccination operators are well designed and utilized. Meanwhile, some theoretical analysis for the local search operators is provided for guiding local search reasonably. The computational results based on 120 well-known benchmark instances and comparisons with some existing algorithms demonstrate the effectiveness of the proposed dispatching rules and the immune algorithm.