臺灣博碩士論文加值系統

本研究探討等速率平行機台(Uniform Parallel Machine)之排程問題，考慮n個工件f個群組在m台等速率平行機台上加工，工件具有抵達時間和群組限制，同一部機台上，如果正準備處理的工件與上一個工件所屬群族不同時，則必須加上整備時間。本研究以總延遲時間最小化為目標。
首先，利用啟發式演算法，將群組排入機台，以減少整備時間，再利用貪婪演算法找出重複時間(Overlap)較大的群組，移除工件並嘗試排入機台上每個位置，排入機台時需考慮工件之抵達時間，直到找到最小總延遲時間則停止。本研究在機台數為30台、群組數為50個、工件量為512個，當處理時間為[1,100]時，求解時間為248.02秒。

We consider the problem of scheduling n jobs with f families on m uniform parallel machines. Every job has arrival time and belongs to one family. We have to add setup time when machine is processing one job( this job’s family is different to last job ). Our objective is to minimize total tardiness.
First, we use heuristic assign family into machine for reducing setup time then we find families with greater overlap and using greedy algorithm to remove jobs from machine . For those jobs witch are removed we try assign them into every position. When we are assigning jobs into machine , we must consider it’s arrival time. The average execution time of problem with 30 machines, 50 families, 512 jobs and processing time [1,00] can be solved in 286.79 seconds.

摘要 I
Abstract II
致謝 III
目錄 IV
圖目錄 V
表目錄 VI
第一章 緒論 1
1.1研究背景與動機 1
1.2範圍與目的 2
1.3研究方法與流程 2
第二章 文獻探討 4
2.1平行機台上總延遲時間之相關文獻 4
2.2 工件具有抵達時間之相關文獻 6
2.3 群組限制之相關文獻 7
第三章 研究方法及模型架構 9
3.1問題描述和定義 9
3.1.1 基本假設 9
3.1.2 符號說明 10
3.2兩階啟發式演算法求解模式 11
3.2.1 啟發式演算法 11
3.2.2 貪婪演算法 12
3.3範例說明 13
第四章結果分析 19
4.1參數設定 19
4.2實驗結果與分析 20
第五章 結論與未來建議 30
5.1結論 30
5.2建議與未來展望 30
參考文獻 31
圖1.1 研究流程 3
圖3.3.1範例結果 17
圖3.3.2移除工件後展示圖 17
圖3.3.3將工件 排入機台1 17
圖3.3.4將工件 排入機台1 18
圖3.3.5將工件 排入機台1 18
圖4.1固定 和 -1 22
圖4.2固定 和 -2 23
圖4.3固定 和 -3 23
圖4.4固定 和 -1 24
圖4.5固定 和 -2 24
圖4.6固定 和 -3 24
圖4.7固定 和 -1 25
圖4.8固定 和 -2 25
圖4.9固定 和 -3 26
圖4.10固定 和 -1 26
圖4.11固定 和 -2 27
圖4.12固定 和 -3 27
圖4.13固定 和 -1 28
圖4.14固定 和 -2 28
圖4.15固定 和 -3 28
表3.3.1問題範例 13
表3.3.2第一次重新編號 14
表3.3.3第二次重新編號 15
表3.3.4第三次重新編號 16
表4.1 實驗參數設定 21
表4.2實驗結果 22
表4.3實驗結果(續) 23

Alidaee, Bahram and Rosa, Duane (1997), 'Scheduling parallel machines to minimize total weighted and unweighted tardiness', Computers & Operations Research, 24 (8), 775-88.

Arkin, Esther M and Roundy, Robin O (1991), 'Weighted-tardiness scheduling on parallel machines with proportional weights', Operations Research, 39 (1), 64-81.
Azizoglu, Meral and Kirca, Omer (1998), 'Tardiness minimization on parallel machines', International Journal of Production Economics, 55 (2), 163-68.
Biskup, Dirk, Herrmann, Jan, and Gupta, Jatinder N. D. (2008), 'Scheduling identical parallel machines to minimize total tardiness', International Journal of Production Economics, 115 (1), 134-42.
Bozorgirad, Mir Abbas and Logendran, Rasaratnam (2012), 'Sequence-dependent group scheduling problem on unrelated-parallel machines', Expert Systems with Applications, 39 (10), 9021-30.
Dessouky, Maged M (1998), 'Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maximum lateness', Computers & Industrial Engineering, 34 (4), 793-806.
Dogramaci, Ali and Surkis, Julius (1979), 'Evaluation of a heuristic for scheduling independent jobs on parallel identical processors', Management Science, 25 (12), 1208-16.
Drobouchevitch, Inna G. and Sidney, Jeffrey B. (2012), 'Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs', Computers & Operations Research, 39 (9), 1919-26.
Du, Jianzhong and Leung, Joseph Y-T (1990), 'Minimizing total tardiness on one machine is NP-hard', Mathematics of operations research, 15 (3), 483-95.
Eom, D-H, et al. (2002), 'Scheduling jobs on parallel machines with sequence-dependent family set-up times', The International Journal of Advanced Manufacturing Technology, 19 (12), 926-32.
Framinan, Jose Manuel and Leisten, Rainer (2008), 'Total tardiness minimization in permutation flow shops: a simple approach based on a variable greedy algorithm', International Journal of Production Research, 46 (22), 6479-98
Guinet, Alain (1995), 'Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria', Journal of Intelligent Manufacturing, 6 (2), 95-103.
Gupta, Jatinder ND and Maykut, Albert R (1973), 'Scheduling jobs on parallel processors with dynamic programming', Decision Sciences, 4 (4), 447-57.
Ho, Johnny C and Chang, Yih‐Long (1991), 'Heuristics for minimizing mean tardiness for m parallel machines', Naval Research Logistics (NRL), 38 (3), 367-81.
Lin, BMT and Jeng, AAK (2004), 'Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs', International Journal of Production Economics, 91 (2), 121-34.

Jin, Feng, Song, Shiji, and Wu, Cheng (2009), 'A simulated annealing algorithm for single machine scheduling problems with family setups', Computers & Operations Research, 36 (7), 2133-38.
Kim, Dong-Won, et al. (2002), 'Unrelated parallel machine scheduling with setup times using simulated annealing', Robotics and Computer-Integrated Manufacturing, 18 (3), 223-31.
Koulamas, Christos (1997), 'Decomposition and hybrid simulated annealing heuristics for the parallel‐machine total tardiness problem', Naval Research Logistics (NRL), 44 (1), 109-25.
Lawler, Eugene L (1964), 'On scheduling problems with deferral costs', Management Science, 11 (2), 280-88.
Lee, Young Hoon and Pinedo, Michael (1997), 'Scheduling jobs on parallel machines with sequence-dependent setup times', European Journal of Operational Research, 100 (3), 464-74.
Lin, Yang-Kuei, Fowler, John W., and Pfund, Michele E. (2012), 'Multiple-objective heuristics for scheduling unrelated parallel machines', European Journal of Operational Research.
Lushchakova, Irina N. (2012), 'Preemptive scheduling of two uniform parallel machines to minimize total tardiness', European Journal of Operational Research, 219 (1), 27-33.
Pfund, Michele, Fowler, John W, and Gupta, Jatinder ND (2004), 'A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems', Journal of the Chinese Institute of Industrial Engineers, 21 (3), 230-41.
Pfund, Michele, et al. (2008), 'Scheduling jobs on parallel machines with setup times and ready times', Computers & Industrial Engineering, 54 (4), 764-82.
Root, James G (1965), 'Scheduling with deadlines and loss functions on k parallel machines', Management Science, 11 (3), 460-75.
Sarıçiçek, İnci and Çelik, Cenk (2011), 'Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness', Applied Mathematical Modelling, 35 (8), 4117-26.
Shim, Sang-Oh and Kim, Yeong-Dae (2007), 'Scheduling on parallel identical machines to minimize total tardiness', European Journal of Operational Research, 177 (1), 135-46.
Suriyaarachchi, Rasika H. and Wirth, Andrew (2004), 'Earliness/tardiness scheduling with a common due date and family setups', Computers & Industrial Engineering, 47 (2-3), 275-88.
Uzsoy, R. (1995), 'Scheduling batch processing machines with incompatible job families', International Journal of Production Research, 33 (10), 2685-708.
Xi, Yue and Jang, Jaejin (2012), 'Scheduling jobs on identical parallel machines with unequal future ready time and sequence dependent setup: An experimental study', International Journal of Production Economics, 137 (1), 1-10.
Yalaoui, Farouk and Chu, Chengbin (2002), 'Parallel machine scheduling to minimize total tardiness', International Journal of Production Economics, 76 (3), 265-79.