本研究主旨在探討無相關平行機台（unrelated parallel machines）上工作不允許佔先（preemption）之排程問題研究，而研究目標為完成時間剛好為該工作交期之工作權重數量最大化。每個工作具有不同的抵達時間，每個工作還須考量機台限制的條件，也就是工作必須由指定的機台集合中的任一機台上進行加工，機台具有可利用時間限制的條件，以及工作具有順序相依性的整備時間（sequence-dependent set-up time），每個工作會因為排入機台上的前一個工作不同，而需要不同的整備時間。本研究目的為針對此問題擬提出啟發式演算法H1，並將所得啟發解作為模擬退火法（simulated annealing）之起始解，近而求得滿意的近似最佳解，並將此結果與陳科甫（2009）使用網路流量（network flow）進行求解之最佳解進行比較，並透過模擬實驗來分析此啟發解之求解品質。模擬退火法在工作數為20時，經實驗設計分析測試，參數因子具有顯著效果，但當工作數為40時，經實驗設計分析測試，參數因子皆無顯著效果，因此本研究中直接使用啟發式演算法H1與數學規劃模式比較求解誤差，經由實驗結果得知，平均求解誤差為3.39 %，求解效率實驗結果得知啟發式演算法H1的平均求解時間約8.99秒，陳科甫（2009）之平均求解時間為662.611秒。

We consider the unrelated parallel machines with sequence-dependent setup times problem. The objective is using Simulated Annealing 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. Setup magnitude of a job depends on its immediately preceding job on the same machine. And we compared with Chen （2009） to find the deviation . And the computation result will be report.

目 錄
摘要 I
Abstract II
誌 謝 III
目 錄 IV
表目錄 VII
第一章 緒論 1
1.1 研究之背景及目的 1
1.2 研究範圍與內容 1
1.3 研究方法 2
第二章 文獻探討 4
2.1 Just-in-time相關文獻 4
2.2 模擬退火演算法 5
2.3 機台限制、機台可利用區間、順序相依性整備時間之相關文獻 6
第三章 模式建構 9
3.1 本研究之基本假設 9
3.2 符號說明 10
3.3 Rm,NCwin│rj,setup,Mj│ΣwjUj問題定義 11
3.4 模擬退火法之起始解 12
3.4.1 啟發式演算法H1 13
3.4.2 解讀編碼之演算法 17
3.4.3 模擬退火演算法 28
第四章 結果分析 32
4.1 實驗參數設定 32
4.2 模擬退火演算法之實驗參數設計 34
4.3 實驗結果分析 37
第五章 結論與未來展望 43
5.1 結論 43
5.2 建議與未來展望 43
參考文獻 45

圖目錄
圖1.1研究流程圖 3
圖3.1排程S，且工作k排在工作j之後 12
圖3.2 Step 1示意圖 16
圖3.3 Step 3- i之示意圖 16
圖3.4啟發解之甘特圖 17
圖3.5編碼示意圖 18
圖3.6解空間之示意甘特圖 18
圖3.7擾動機制示意圖 19
圖3.8遇機台限制之特殊情況 19
圖3.9工作k排入機台的最早開始時間，且工作k排在工作j之後 21
圖3.10遇機台空間不足夠排入編碼中所有工作之特殊情況 24
圖3.11P1,5排入Just-in-time後機台空間不足讓剩餘工作與整備時間排入 27
圖3.12模擬退火演算法流程圖 31
圖4.1實驗參數因子對演算法H1求解誤差之關係圖 38
圖4.2實驗參數因子對演算法H1求解時間之關係圖 39


表目錄
表3.1　演算法範例資料表(一） 15
表3.2　演算法範例資料表（二） 15
表4.1　實驗參數設定表 34
表4.2　實驗參數設定表 35
表4.3　模擬退火實驗設計結果 36
表4.4　 n=20，m=3實驗設計之ANOVA分析 36
表4.5　啟發式演算法與數學規劃模式求解誤差表（λ=0.2） 40
表4.6　啟發式演算法與數學規劃模式求解誤差表（λ=0.5） 41
表4.7　啟發式演算法與數學規劃模式求解誤差表（λ=1） 42

陳科甫 (2009), “平行機台下Just-in-time工作權重個數最大化之排程問題”.
汪定偉、王俊偉、王洪峰、張瑞友、郭哲 (2008), “智能優化方法”.
Andresen M., Brasel H., Morig M., Tusch J., Werner F., Willenius P., (2008), “Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop,” Mathematical and Computer Modelling, 48, 1279–1293.
Baker K.R., (1974), “Introduction to Sequencing and Scheduling,” Wiley, New York.
Breit J., Schmidt G., Strusevich V. A., (2001), “Two-machine open shop scheduling with an availability constraint,” Operations Research Letters 29, 65–77.
Centeno G., Armacost R.L., (1997), “Parallel machine scheduling with release time and machine eligibility restrictions.” Computers & Industrial Engineering, 33（1-2）,273-276.
Behnamian J., Zandieh M., Ghomi S.M.T. F, （2009）, ” Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm,” Expert Systems with Applications , 36, 9637 – 9644.
Centeno G., Armacost R.L., (2004), “Minimizing makespan on parallel machines with release time and machine eligibility restrictions,” International Journal of Production Research, 42（6） 1243-1256.
Cepek O., Sung S. C. , （2005）, “A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines,” Computers & Operations Research, 32, 3265–3271.
Daya M. Ben , Fawzan M. A1, (1996), “A simulated annealing approach for the one-machine mean tardiness scheduling problem,” European Journal of Operational Research, 93, 61-67.
Huegler , Vasko, (1997), “A performance comparison of heuristics for the total weighted tardiness problem,” Computers & Industrial Engineering, 32(4), 753 - 767.
Hiraishi K., Levner E., Vlach M., (2002), “Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs,” Computers & Operations Research, 29(7), 841–848.
Hendel Y., Runge N. and Sourd F. , (2009), “The one-machine just-in-time scheduling problem with preemption,” Discrete Optimization, 6, 10 - 22.
Jin F., Song S., Wu C., (2009), “A simulated annealing algorithm for single machine scheduling problems with family setups,” Computers & Operations Research, 36, 2133–2138.
Jabbarizadeh F., Zandieh M., Talebi D., (2009), “Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints.” Computers & Industrial Engineering.vol.56 Issue.4 1452-1463.
Kirkpatrick S., Gelatt C. D., Vecchi M. P., (1983), “Optimization by Simulated Annealing,” Science, New Series, 220, 671-680.
Kim D. W., Kim K. H., Jang W., Chen F. F., (2002), “Unrelated parallel machine scheduling with setup times using simulated annealing,” Robotics and Computer Integrated Manufacturing, 18, 223–231.
Krajewski L.J., King B.E., Ritzman L.P., Wong D.S., （1987）, “Kaban, MRP and shaping the manufacturing environment,” Management Science, 33, 39–57.
Kubzin M. A., Potts C. N., Strusevich V. A., （2009）, ” Approximation results for flow shop scheduling problems with machine availability constraints,” Computers & Operations Research , 36, 379 – 390.
Lann A., Mosheiov G, (1996), “Single machine scheduling to minimize the number of early and tardy jobs,” Computers & Operations Research 23, 765–781.
Low C., (2005), “Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines,” Computers & Operations Research, 32, 2013–2025.
Liao L.W., Sheen G.J. , （2008）, ”Parallel machine scheduling with machine availability and eligibility constraints.” European Journal of Operations Research,184,458-467.
Liu C. Y., Chang S. C., (2000), “Scheduling flexible flow shops with sequence-dependent setup effects,” IEEE Transactions on Robotics and Automation, 16 (4), 408–419.
Lebacque V., Jost V., Brauner N., （2007）, ” Simultaneous optimization of classical objectives in JIT scheduling,” European Journal of Operational Research, 182, 29–39.
Lee K., Leung J. Y.-T., Pinedo M. L., （2009）, ” Online scheduling on two uniform machines subject to eligibility constraints,” Theoretical Computer Science, 410, 3975–3981.
Mellouli R., Sadfi C., Chu C., Kacem I., (2007), “Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times,” European Journal of Operational Research, 197, 1150–1165.
Mati Y., （2010）, ” Minimizing the makespan in the non-preemptive job-shop scheduling with limited machine availability,” Computers & Industrial Engineering, 19, 89–97.
Metropolis N., Rosenbluth A., Rosenbluth M., Teller A., (1953), “Equation of state calculations by fast computing machines,” Journal of Chemical Physics, 21, 1087-1092.
Naderi B., Ghomi S.M.T. F., Aminnayeri M., (2010), “A high performing metaheuristic for job shop scheduling with sequence-dependent setup times,” Applied Soft Computing, 10, 703–710.
Naderi, Zandieh M., Ghomi Fatemi (2008), “Scheduling job shop problems with sequence dependent setup times.” International Journal of Production Research, 10 1366-5881.
Paula M.R.D., Mateus G. R., Ravetti M.G., （2009）, ” A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times,” Computers & Operations Research , 37, 938 – 949.
Roshanaei V., Esfehani M. M. S., Zandieh M., (2010), “Integrating non-preemptive open shops scheduling with sequence-dependent setup times using advanced metaheuristics,” Expert Systems with Applications, 37, 259–266.
Rabadi G., Georgios C., Anagnostopoulos, Mollaghasemi M., (2007), “A heuristic algorithm for the just-in-time single machine scheduling problem with setups: a comparison with simulated annealing,” The International Journal of Advanced Manufacturing Technology, 32, 326–335.
Schmidt G.., (1984), “Scheduling on semi-identical processors.” Zeitschrift f fur Operations Research, A28153-162.
Schmidt G.., (1984), “Scheduling independent tasks with deadlines on semi-identical processors.” Journal of the Operational Research Society, 39, 271-277.
Sung S. C., Vlach M. , （2005）, “Maximizing weighted number of just-in-time jobs on unrelated parallel machines,” Journal of Scheduling,8 453-460.
Tuong N. H., Sounhal A. , （2010）, “Due dates assignment and JIT scheduling with equal-size jobs,” European Journal of Operational Research, 205, 280–289.
Tuong N. H., Sounhal A. , （2008）, “Some New Polynomial Cases In Just-In-Time
Scheduling Problems with Multiple Due Dates,” Proceeding of the Sixth International
conference on Research, Innovation and Vision for the Future in Computing and Communications Technologies, pp. ISBN 978-1-4244-2379-8, 36–41.
Wan G., Yen B. P.-C., （2009）, ” Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs,” European Journal of Operational Research, 195, 89–97.
Zandieh M., Ghomi S. M. T. Fatemi , Hosseini S. M. Moattar, （2006）, ”An immune algorithm approach to hybrid flowshops scheduling with sequence-dependent setup times,” Applied Mathematics and Computation, 180, 111–127.