Scheduling permutation flow shops using the Lagrangian relaxation technique

Flow shop is a common manufacturing environment for the production of multiple types of similar products. A permutation flow shop is a special kind of flow shop where processing sequences at all production stages are physically constrained to be the same. These ‘identical sequence constraints’ couple the processing sequences of various production stages, making it difficult to have a separable problem formulation which is critical for obtaining near-optimal schedules by using the Lagrangian relaxation technique. This paper presents a novel ‘separable’ integer programming formulation for permutation flow shops. The objective is to minimize penalties on production tardiness and on releasing raw materials too early subject to relevant constraints. After coupling constraints are relaxed by using Lagrange multipliers, the problem is decomposed into individual subproblems that can be solved without much enumeration. The multipliers are updated at the high level by using the recently developed Reduced Complexity Bundle Method. The ‘inherent duality gap’ is proved to exist in general, implying that the quality of a schedule generated may be higher than what is indicated by its relative duality gap. Testing results show that the algorithm can be effectively used to solve practical scheduling problems.