雙階段流程型工廠在有限等待時間限制下之排程問題

The Two-Stage Flowshop Sequencing Problem with Limited Waiting Time Constraint

黃淑娟(Shu-Juan Huang)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200100406

摘要

本研究旨在探討雙階段流程型工廠在有限等待時間限制下之排程問題，其衡量指標為同時考量總完成時間 (Makespan) 及總流程時間 (Total Flow Time) 之雙目標函數，而此問題之複雜度早已被證明為NP-hard，因此本研究發展一啟發式求解法則，以縮短求解時間並使求解品質達一定之水準。所謂有限等待時間乃是在第一個階段製程加工完成到第二個階段製程加工間的等待時間不可超過其預設的限制值。
本研究分兩部份來探討，第一部份探討雙階段皆為單機且單次加工單一工件，其設置時間 (Setup Time) 與加工時間 (Processing Time) 分開之排程問題；第二部份則探討第一階段製程為批量式生產，每一工件在此機器之加工時間為固定值且每一批量有產能限制，而第二階段製程為單次加工單一工件。
本研究先採用凍結事件程序 (Frozen-event procedure) 將第一部份之雙階段流程型工廠排程之動態問題轉換成靜態排程問題。針對二部份之靜態排程問題分別提出啟發式排程演算法，並分別建立整數規劃模式，以驗證啟發式排程演算法之正確性，及作為評估啟發式排程演算法求解品質之基準。

關鍵字

批次處理 ； 雙階段流程型工廠 ； 有限等待時間 ； 雙目標

並列摘要

In this study we consider the two-stage flowshop sequencing problem with limited waiting time constraint. This means that for each job the waiting time between two stages cannot be greater than a given upper bound. The performance considered is the simultaneous minimization of total flow time and makespan.
Two cases are considered in this study. In the first case where in one discrete processor is incurred in each two stage while in the second case batch processing is incurred in the first stage with limited capacity. A frozen-event procedure is proposed to transform dynamic scheduling problem into static ones. For each case, the corresponding heuristic scheduling algorithm is developed. Integer programming models are formulated to validate the performance of those heuristic scheduling algorithms.

並列關鍵字

batching scheduling ； bicriteria ； two-stage flowshop ； limited waiting time constraint

參考文獻

4. Adiri, I. and D. Pohoryles, 1982, Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times. Naval Research Logistics Quarterly, 29, 495-504.

5. Ahmadi, J. H., Ahmadi, R. H., Dasu, S. and Tang, C. S., 1992, Batching and scheduling jobs on batch and discrete processors. Operations Research, 39(4), 750-763.

6. Aldowaisan, T. and A. Allahverdi, 1998, Total flowtime in no-wait flowshops with separated setup times. Computers and Operations Research, 25(9), 757-765.

7. Allahverdi, A., 1997, Scheduling in stochastic flowshop with independent setup, processing and removal times. Computers and Operations Research, 24, 955-960.

8. Glassey, C. R. and W. W. Weng, 1991, Dynamic batching heuristics for simultaneous processing. IEEE Transactions on Semiconductor Manufacturing, 4, 77-82.