本研究針對無相關平行機台（unrelated parallel machines）上工作不允許佔先（preemption）之排程問題研究，研究目標為完成時間剛好為該工作交期之工作權重數量最大化。每個工作具有不同的抵達時間，每個工作還須考量機台限制的條件，也就是工作必須由指定的機台集合中的任一機台上進行加工。而除此之外而機台具有可用時間限制的條件。另外，工作具有順序相依性的整備時間（sequence-dependent Set-up Time），每個工作會因為排入機台上的前一個工作不同，而需要不同的整備時間。本研究對此問題擬提出最佳解求解方式，此求解方式將原始問題轉化為運用網路流量（network flow）進行求解的轉運問題（Transshipment Problem），進而設計轉運問題的數學規劃模式以求得最佳解，並透過模擬實驗分析此求解方式之求解效率，模擬中最大環境工作數量150個，機台10台，最佳解的平均求解時間約202秒。

We study the problem of non-preemptively scheduling jobs on unrelated parallel machines with the objective to maximize the weighted number of jobs that are completed exactly at their due date. Each job has different arrival time and can only be processed on specified machines. Each machine is not continuously available at all times. Another common assumption is the consideration of sequence-dependent setup times. Setup magnitude of a job depends on its immediately preceding job on the same machine. We propose an optimal algorithm for this problem. We propose a optimal algorithm for this problem. And the computation result will be report.

目錄
中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
圖目錄 v
表目錄 vi
第一章 緒論 1
1.1 研究背景與目的 1
1.2 研究範圍與內容 1
1.3 研究方法 2
第二章 文獻探討 4
2.1 just-in-time工作個數最大化相關文獻 4
2.2 其他限制條件相關文獻 5
第三章 模式建構 6
3.1 本研究之基本假設 6
3.2 符號說明 7
3.3 問題定義 8
3.4 問題 9
3.4.1 數學建構模式 9
3.4.2 例子 13
第四章 結果分析 18
4.1 實驗參數設定 18
4.2 實驗結果與分析 22
第五章 結論與未來展望 29
5.1 結論 29
5.2 建議與未來展望 29
參考文獻 30

圖目錄
圖1.1 研究流程圖 3
圖3.1排程S，且工作 排在工作 之後 8
圖3.2有向網圖 及權重函數表示圖 16
圖3.3範例最佳解 18
圖3.4最佳解之甘特圖 18
圖4.1機台可利用區間產生示意圖 20
圖4.2因子 與平均求解時間關係圖 26
圖4.3因子 與平均求解時間關係圖 26
圖4.4因子 與平均求解時間關係圖 27
圖4.5因子 與平均求解時間關係圖 28

表目錄
表3.1演算法範例資料表(一） 14
表3.2演算法範例資料表(一） 14
表4.1實驗設計（一） 21
表4.2各因子對求解時間ANOVA分析（一） 22
表4.3各因子對求解時間ANOVA分析（二） 23
表4.4平均求解時間表 24
表4.5最大求解時間表 25

[1]G.. Schmidt（1984）“Scheduling on semi-identical processors.” Zeitschrift f fur Operations Research, A28153-162.

[2]G.. Schmidt（1988）“Scheduling independent tasks with deadlines on semi-identical processors.” Journal of the Operational Research Society, 39, 271-277.

[3]C. Chu （1992）“A Branch-And-Bound Algorithm to Minimize Total Tardiness with Different Release Date.”Naval Research Logistics, 39 265-283

[4]A. Lann and G. Mosheiov (1996), “Single machine scheduling to minimize the number of early and tardy jobs,” Computers & Operations Research 23, 765–781.

[5]G. Centeno, R.L. Armacost. （1997）“Parallel machine scheduling with release time and machine eligibility restrictions.” Computers & Industrial Engineering, 33（1-2）,273-276.

[6]K. Hiraishi, E. Levner, and M. Vlach (2002),“Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs,” Computers & Operations Research, 29(7), 841–848.

[7]O. Alagoz & M.Azizoglu （2003）“Rescheduling of identical parallel machines under machine eligibility constraints.” European Journal of Operations Research, 149 523-532.

[8]O. Cepek and S. C. Sung （2004）, “A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines,” Computers & Operations Research, 32 3265–3271

[9]G. Centeno, R.L. Armacost.（2004）“Minimizing makespan on parallel machines with release time and machine eligibility restrictions.” International Journal of Production Research, 42（6） 1243-1256.



[10]S. C. Sung and M. Vlach （2005）,“Maximizing weighted number of just-in-time jobs on unrelated parallel machines,”Journal of Scheduling,8 453-460.

[11]F. S. Hillier and G. J. Lieberman （2005）Introduction to operation research. McGraw-Hill Education ,Asia.

[12]M. Zandieh, S. M. T. Fatemi Ghomi & S. M. Moattar Hosseini (2006). “An immune algorithm approach to hybrid flowshops scheduling with sequence-dependent setup times, ” Applied Mathematics and Computation, 180, 111–127.

[13]J. F. Chen （2006）“Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups.” The International Journal of Advanced Manufacturing ,29 ,557-563

[14]B. Naderi, M. Zandieh, S.M.T. Fatemi Ghomi (2008). “Scheduling job shop problems with sequence dependent setup times. ” International Journal of Production Research, 10 1366-5881

[15]L.W. Liao, G.J. Sheen. （2008）“Parallel machine scheduling with machine availability and eligibility constraints.” European Journal of Operations Research,184,458-467

[16]F. Jabbarizadeh , M. Zandieh , D. Talebi （2009）“Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints.”Computers & Industrial Engineering.vol.56 Issue.4 1452-1463.