Solving proportionate flexible flow shop scheduling problems: A column generation approach

Der Fang Shiau, Yueh Min Huang

研究成果: Conference article同行評審

1 引文 斯高帕斯(Scopus)

摘要

This paper aims to illustrate a flow shop scheduling problem in which the processing time of each operation of job j is equal to pj. This class of the flow shop problem is known as the proportionate flow shop problem. A proportionate flexible flow shop problem is generalization of the proportionate flow shop problem with multiple identical machines at any stage. The general WSPT rule minimizes the total weighted completion time in the case of a single machine. Unfortunately, this result cannot be generalized to parallel machines. We propose a decomposition approach applied to a Restricted Master Problem (RMP) with a set covering formulation in which the linear programming relaxation is solved efficiently by column generation. If the linear programming relaxation forms to be integral, an optimal solution for the problem is obtained. Otherwise, we apply a branch and bound algorithm which is based on the completion time of jobs appearing in a fraction solution, through some computational results, the effectiveness and the capability of solving large scale problems. Finally, the proposed approach is proven to be able to effectively minimize the total weighted completion time for the proportionate flexible flow shop problem by some analyses.

原文English
頁(從 - 到)417-422
頁數6
期刊Proceedings of the IASTED International Conference on Modelling, Simulation, and Optimization
出版狀態Published - 2004 十二月 27
事件Proceedings of the Fourth IASTED International Conference on Modelling, Simulation, and Optimization - Kauai, HI, United States
持續時間: 2004 八月 172004 八月 19

All Science Journal Classification (ASJC) codes

  • 軟體
  • 建模與模擬
  • 電腦科學應用

指紋

深入研究「Solving proportionate flexible flow shop scheduling problems: A column generation approach」主題。共同形成了獨特的指紋。

引用此