- 學位論文
以單機及平行機排程問題比較多種混合整數規劃模式
The Comparison of MILP Formulations: Single Machine vs. Parallel Machine Scheduling Problems
摘要
製造業之生產型態中，常見的生產型態有單機(Single Machine)、流程式生產(Flow Shop)、平行機台(Identical Parallel Machine)、零工式生產(Job Shop)以及開放式生產(Open Shop)，其中又以單機排程最為重要，因所有生產型態中單機為最基本之排程型態，而多台單機同時彼此獨立作業為平行機排程，平行機排程型態被不同產業大量運用，常見的平行機排程應用為半導體封裝測試及生活中常見服務業之服務櫃台，因此平行機生產排程型態為一個相當重要的議題。 本研究主要探討單機排程與平行機排程問題，並用四種不同混合整數規劃模式(Mixed-Integer Linear Programming; MILP)建構數學模型，以LINGO語言編碼求解，比較不同排程環境下不同混合整數規劃模式之優劣。其目標為總完工時間(Total Completion Time)與最大完工時間(Maximum Completion Time)最小化，為測試不同混合整數規劃模式之求解績效與品質，本研究設計不同題庫進行測試，並對求解結果以SPSS進行統計分析，結果顯示不同情況四種混合整數規劃之求解績效具有顯著差異，研究結果可供未來相關研究以及產業做為參考。
並列摘要
In the manufacturing industry, the most types are single machine, flow shop, identical parallel machine, job shop, and open shop. The most important type is single machine, since it is the most basic type of scheduling. Many single machines working at the same time independently is called parallel machine scheduling, which is applied in many different kinds of manufacturing industry. The application of parallel machine scheduling is often seen in semiconductor packaging and testing and the service counter in daily life. So, the parallel machine scheduling is quite an important issue. In this research, the author mainly probes the question of single machine and parallel machine scheduling, using four different kinds of mixed-integer linear programming (MILP) to construct math models, finding the solutions by LINGO language code and compares the pros and cons in different scheduling environment and different MILP. The target of this research is to minimize the total completion time and maximum completion time. In order to test the efficacy and quality of different MILP, this research designs different question database for testing and analyzes the solution by SPSS. The result shows that the efficacy of solutions in four different kinds of MILP has great differences. The result of this research can provide reference materials for further study in the future.