多製程平行機之流程型工廠總加權完工時間最小化問題

A Multi-stage Parallel-processor Flowshop Problem With Minimum Total Weighted Completion Time

吳泓葦(Hung-Wei Wu)

指導教授 ： 蘇玲慧

中原大學/工學院/工業工程研究所/碩士(2002年)

https://doi.org/10.6840/cycu200200581

摘要

本論文針對多階段平行機之流程型(Flow-shop with parallel machines)工廠之排程問題加以探討，並考慮各工作有不同重要性給予不同權重，以最小化所有工件加權完工時間為目標(Total weighted completion time)，在此生產型態中，每一製程階段有多台等效平行機，工件依序經由每一製程階段中任意一台機器加工即可。由於此類排程問題為一NP-Hard，因此發展塔布演算法，以縮短求解時間，但無法應用整數規劃求得整體之最佳解，因此分別針對各製程階段皆同一加工順序，及只決定第一製程階段之加工順序，第二製程階段以後皆採先到先加工之機制兩種不同的條件限制下發展分支界限演算法求取一最佳加工順序，作為衡量塔布演算法求解品質之指標。

關鍵字

流程型工廠 ； 平行機 ； 權重 ； 塔布演算法

並列摘要

The problem of scheduling in multi-stage flow-shop with parallel machines with the objective of minimizing the total weighted completion of jobs. In this manufacturing system each part must be processed by at most one machine in each stage. Since the flow-shop scheduling problem is NP-Hard, a Tabu algorithm is proposed, and developed an branch and bound algorithm to validate the performance of the tabu algorithm.

並列關鍵字

weight ； flow-shop ； tabu algorithm ； parallel machine

參考文獻

3. A.B. Shaukat, J.L. Hunsucker, 1991,“Branch and bound algorithm for the flow shop with parallel processors,”European Journal of Operational Research 51, pp.88-99.

4. Azizoglu, M., Cakmak, E., Kondakci S., 2001,“A flexible flowshop problem with total flow time minimization,” European Journal of Operational Research, 132, 528-538.

5.Azizoglu, M., and Kirca, O., 1999,“On minimization of total weighted flow time with identical and uniform parallel machines,”European Journal of Operational Research, 113, 91-100.

6.Barnes, J.W. and Laguna, M., 1993,“Solving the multiple-machine weighted flow time problem using tabu search,”IIE Transactions, 25, 2, 121-128.

7.Brah, S.A., and Hunsucker, J.L., 1991,“Branch and bound algorithm for the flow shop with multiple processors,”European Journal of Operational Research, 51, 88-99.