A novel decoding method for the hybrid flow-shop scheduling problem with multiprocessor tasks

摘要

As the strongly NP-hard problem, the hybrid flow-shop problem with multiprocessor tasks (HFSPMT) has gained increasing attention due to its academic significance and wide application background. For many heuristics and meta-heuristics to solve the HFSPMT, decoding method is the key element to decode sequences to schedules, which has great effect on the solution quality. To narrow the idle time between the consecutive operations in the processor and to increase the flexibility in selecting processors to schedule the following operations, several rules are proposed to adjust sequences to minimize the makespan of the HFSPMT. Based on the rules, a novel and effective decoding method named forward scheduling (FS) is proposed in this paper for solving the HFSPMT. At each stage, it first decodes the solution according to the non-decreasing order of the jobs' completion times at the previous stage, and then it adjusts the processing order of the jobs dynamically according to the rules to obtain potentially better schedule. Numerical results based on the well-known benchmarks and comparisons with some existing decoding methods demonstrate the effectiveness of the proposed FS decoding method.