Heuristics and metaheuristics to minimize makespan for flowshop with peak power consumption constraints

Abstract

This paper addresses the permutation flowshop scheduling problem with peak power consumption constraints (PFSPP). The real-time power consumption of the PFSPP cannot exceed a given peak power at any time. First, a mathematical model is established to describe the concerned problem. The sequence of operations is taken as a solution and the characteristics of solutions are analyzed. Based on the problem characteristics, eight heuristics are proposed, including balanced machine-job decoding method, balanced machine-job insert method, balanced job-machine insert method, balanced machine-job group insert method, balanced job-machine group insert method, greedy algorithm, beam search algorithm, and improved beam search algorithm. Similarly, the canonical artificial bee colony algorithm and iterated local search algorithm are modified based on the problem characteristics to solve the PFSPP. A large number of experiments are carried out to evaluate the performance of new proposed heuristics and metaheuristics. The results and discussion show that the proposed heuristics and metaheuristics perform well in solving the PFSPP.