No-Wait Flowshop Scheduling With Variable Processing Times

No-wait flowshop scheduling with variable processing times is an important kind of com-binatorial optimization problem with constraints, which is widely exists in metallurgy, plastic, textile, chemistry and semiconductor industries. The variety of processing times is usually rep-resented as the learning and deterioration effects in flowshop problems. Among the common used obejective functions of scheduling, the total tardiness minimization is relative to the pro-duce schedule of the enterprises, while its computational difficulty is higher than the one of flowtime minimization or makespan minimization. Therefore, the no-wait flowshop scheduling problem with variable processing time and total tardiness minimization has important theoretical meaning and practical value.A learning and deterioration model based on schedule positions is proposed for no-wait flowshop scheduling with variable processing times. To improve the efficiency for evaluating the objective function values of the solutions newly generated during the search, the objective incremental properties of specific swap operations are inferred in this work. The operators for fast evaluating are constructed and an accelerated iterated local search algorithm is promoted specially for this problem. The algorithm consists of four modules:initial solution generation, local search, perturbation and acceptance criterion. The initial solution module is improved based on a traditional heuristic to deal with the multiple best insertion slots condition which has not been considered in the traditional version. The local search module is designed to include insertion neighborhood structure. The perturbation module is proposed to modify the current solution and to generate candidate solutions. The acceptance criterion module decides whether the newly generated solution can replace the current solution to attend the following search procedures. The execution of the algorithm stops once the terminal criterion is satisfied, and the best solution found is returned.To verify the efficiency and effectiveness of the promoted algorithm, the rules selected for modules and the parameters in the algorithm are tested in the experiments and tuned by analysis of variance. Based on a standard instance set, the promoted algorithm is compared with the best algorithm which solves similar problems. The experiments demonstrated that the promoted algorithm outperforms the existing algorithm.