Heuristics for scheduling in flowshop with multiple objectives

Most of the heuristics for flowshop scheduling aim at minimizing makespan. However, scheduling with multiple objectives, such as that of minimizing makespan, total flowtime and machine idletime, is more effective in reducing the total scheduling cost. In this article, we first address the problem of scheduling to minimize makespan and total flowtime, and propose a new heuristic algorithm. A heuristic preference relation is developed as the basis for the heuristic so that only the potential job interchanges are checked for possible improvement with respect to these two objectives. The proposed as well as the existing heuristics are evaluated in a large number of randomly generated large-sized problems. The proposed heuristic algorithm is then extended to cover the problem of scheduling to minimize makespan, total flowtime and machine idletime. The results of the experimental investigation of the evaluation of this heuristic algorithm and the existing heuristic in meeting these objectives are also reported. It is found that both the proposed heuristics are more effective than the existing one for scheduling with multiple objectives.