雙階段流程型工廠延遲工作數最小化之排程問題

Two-machine flowshop scheduling to minimize the number of tardy jobs

謝婉玲(Wan-Ling Shie)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200400417

摘要

本研究主旨在探討雙階段流程型工廠，第一階段製程為批次生產機台，第二階段製程為單機生產機台。其批次機台的批次加工時間固定且批次容量固定為Z，在每個工作擁有不同的到期日下求解總延遲工作數最小化之排程問題。由於此問題已被證明為NP-Hard問題，因此本研究發展出一有效的啟發式排程演算法，可快迅且有效的求得最佳解或近似最佳解。同時並針對此問題提出下限值求法及問題特性用以建立分支界限方法，來驗證啟發式演算法之求解品質。其求解過程與實驗結果會在本研究中詳述。

關鍵字

啟發式演算法 ； 雙階段流程型工廠 ； 批次機台

並列摘要

This paper considers a hybrid two-stage flowshop problem with a batch processor in stage 1 and a discrete processor in stage 2. Each batch processor can process Z jobs simultaneously and has the fixed processing time. The objective is to minimize the total number of tardy jobs. This problem is shown to be NP-hard. Several properties and lower bound are developed. A heuristic algorithm and a branch and bound algorithm are proposed. The performance ratios of the heuristic algorithm and computational results are presented.

並列關鍵字

heuristic algorithms ； two-machine flowshop ； batch processing machine

參考文獻

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

Baptiste, P., Peridy, L. and Pinson, P.(2003), “A branch and bound to minimize the number of late jobs on a single machine with release time constraints,” European Journal of Operational Research, vol.144, pp.1-11.

Bulfin, R.L. and M’Hallah R.(2003), “Minimizing the weighted number of tardy jobs on a two-machine flow shop,” Computer and Operations Research, vol.30, pp.1887-1900.

Chen, C.L. and Bulfin, R.L.(1994), “Scheduling a single machine to minimize two criteria：maximum tardiness and number of tardy jobs,” IIE Transactions, vol.26, pp.76-84.

Croce, F.D., Gupta, J.N.D. and Tadei, R.(2000), “Minimizing tardy jobs in a flowshop with common due date,” European Journal of Operational Research, vol.120, pp.375-381.