A Decomposition and Coordination Scheduling Method for Flow-shop Problem Based on TOC
-
摘要: There are many flow shop problems of throughput (denoted by FSPT) with constraints of due date in real production planning and scheduling. In this paper, a decomposition and coordination algorithm is proposed based on the analysis of FSPT and under the support of TOC (theory of constraint). A flow shop is at first decomposed into two subsystems named PULL and PUSH by means of bottleneck. Then the subsystem is decomposed into single machine scheduling problems, so the original NP-HARD problem can be transferred into a serial of single machine optimization problems finally. This method reduces the computational complexity, and has been used in a real project successfully.
-
关键词:
- Flow-shop scheduling /
- TOC /
- bottleneck /
- decomposition /
- coordination
Abstract: There are many flow shop problems of throughput (denoted by FSPT) with constraints of due date in real production planning and scheduling. In this paper, a decomposition and coordination algorithm is proposed based on the analysis of FSPT and under the support of TOC (theory of constraint). A flow shop is at first decomposed into two subsystems named PULL and PUSH by means of bottleneck. Then the subsystem is decomposed into single machine scheduling problems, so the original NP-HARD problem can be transferred into a serial of single machine optimization problems finally. This method reduces the computational complexity, and has been used in a real project successfully.-
Key words:
- Flow-shop scheduling /
- TOC /
- bottleneck /
- decomposition /
- coordination
计量
- 文章访问数: 2282
- HTML全文浏览量: 52
- PDF下载量: 1571
- 被引次数: 0