應用動態規劃演算法於單機排程流程工廠之研究

A Study on the Dynamic Programming Approach to Single Machine Scheduling Flow Shop

張昱敬(Yu-Jing Chang)

指導教授 ： 林逾先

國立臺北科技大學/管理學院/商業自動化與管理研究所/碩士(2005年)

https://doi.org/10.6841/NTUT.2005.00076

摘要

近年來，在貿易自由化、國際化的趨勢下，企業紛紛面臨客戶縮短交貨期限的需求，企業除引進新科技以快速回應全球供貨的需求外，如何運用良好的生產排程在約定日期內將產品生產完成送交至客戶手中更顯得日益重要，除可降低生產總成本外亦可使利潤極大化，而單機具到期日之排程(Job-Scheduling with Deadlines；JSD)可有效解決此類生產排程問題，亦是本研究所關心的，單機具到期日之排程可視為單機排程的應用，它是以到期日為派工法則，主要可應用在JIT製造系統、流程工廠等。而單機具到期日之排程流程工廠(flow shop)的特性是指在具到期日的時間限制下，所有的工件都具有相同的處理程序，換言之，每一工件須經過一部以上的機器加以處理且順序是一致的，例大量生產的生產線，如何運用良好的生產排程使流程工廠生產效益極大化是本研究所要探討的重點。
單機排程的解法可分兩類，第一類為啟發式演算法及局部搜尋法等，一般而論針對特殊問題所設計的啟發式演算法其求解績效皆十分理想，且求解時間亦相當迅速。而在局部搜尋法方面有塔布搜尋法（Tabu Search）等，第二類為最佳化方法如動態規劃（Dynamic Programming）、分枝界限法（ Branch and Bound）等。其求解時間一般而言遠大於啟發法及局部搜尋法，但以最佳化方法所求得的最佳解可用來當作績效評估準則，因此最佳化方法仍有存在之必要。
到目前為止，己有研究利用多期與多重選擇背包問題（Multiple-Choice Multi-Period Knapsack Problem; MMKP）建立表示單機排程之數學模式，並以分支界限法求解，證實能在極短時間內得到最佳解，而目前尚無以動態規劃觀點求解MMKP的研究，因此本篇論文主軸為應用動態規劃法求解在有限時間下的單機流程工廠(Flow shop)，使工件從進入系統到離開系統的總效益最大的問題。首先我們運用MMKP建立表示單機排程流程工廠的數學模式，接著運用動態規劃演算法求算MMKP，最後再以IBM APL2程式語言實作MMKP測試問題。實驗結果發現利用動態規劃演算法求解期數較少的MMKP問題所花的時間和分支界限法相去不遠，但亦可同時找出所有可能的最佳解，在求解多期的MMKP上還是以分支界限法的速度較佳。

關鍵字

單機排程 ； 流程工廠 ； 動態規劃 ； 分支界限法 ； 多期與多重選擇背包問題

並列摘要

無資料

並列關鍵字

Single-job scheduling ； Flow shop ； Dynamic programming ； Branch and Bound Algorithm ； Multiple-choice multi-period knapsack problem

參考文獻

[3] Hamdy A. Taha, 2004, Operations Research, Pearson Education, Inc pp.401-415

[5] Thiel, J. and Voss, S., "Some experiences on solving multiconstraint zero-one knapsack problems with genetic algorithm," INFOR, 32, 1994 pp. 226–242.

[6] Senju S and Toyoda. Y., "An approach to linear programming with 0-1 variables," Management Science, 15, 1968, B 196–207.

[7] Toyoda. Y, "A simplified algorithm for obtaining approximate solutions to zero-one programming problems," Management Science, 21, 1975, pp 1417–1427.

[8] G. V. Gens and E. V. Levner, "Fast approximation algorithm for job sequencing with deadlines," Discrete Applied Mathematics, no. 3, 1981, pp. 313-318.