A relaxation heuristic for scheduling flowshops with intermediate buffers

The paper presents a two-level relaxation heuristic for production planning for multistage flowshop systems with intermediate buffers. The method concerns unidirectional multistage systems where tasks with respect to many various types of products are performed simultaneously. The fixed and the alternative production routes are regarded in the method. The top-level is a stage loading, i.e., allocation of tasks among the stages. The base-level is a task scheduling - allocation of tasks among the stations. The linear mathematical models of mixed integer programming are used in the method. The time criterion is used in the minimization functions - the minimal schedule is fixed. The condition that variables are to be integers has been ignored in the heuristic. The relaxed heuristic developed in such a manner enables obtaining good results in a very short time. This paper discusses the multilevel approach as the developed production scheduling method serves the purpose of solving relatively large problems. Results of computational experiments with the proposed heuristic method are presented.