Lagrangian relaxation algorithms for hybrid flow-shop
scheduling problems with limited buffers

Takashi Irohara

Faculty of Science and Technology

Sophia University
7-1 Kioi-cho, Chiyoda-ku,
Tokyo, 102-8554, Japan
E-mail: irohara@sophia.ac.jp

Abstract: In this research, Lagrangian relaxation algorithms are proposed for Hybrid Flow-Shop (HFS) scheduling problems. Conventional HFS consists of a series of production stages, each of which has several identical parallel machines and no buffer spaces are considered. Jobs are processed through all stages in the same direction. In the previous researches, they are assumed that the capacity of buffer is infinite. But in the actual manufacturing environment, the maximum capacity of buffer is limited. That's why HFS with limited buffer is studied in this research. Unrelated parallel machine is the general and important model of parallel machine, because this is the model which can consider the difference of machining performance with large flexibility. But most studies of HFS deal with identical parallel machines which do not consider the machine abilities. These are the motivation to study HFS scheduling problem with unrelated parallel machine in this study. In this research, the objective function is to minimize the total weighted tardiness and the earliness for each job. Three methods of Lagrangian relaxation algorithms are proposed to solve the HFS scheduling problem with limit buffers. In most studies about Lagrangian relaxation algorithm, the machine capacity constraints are relaxed and each stage is scheduled separately. But in this study, not only the machine capacity but also the precedence constraints are relaxed to schedule all stages together. The results of numerical experiments showed that the proposed methods perform very well especially for large scale problems.