臺灣博碩士論文加值系統

　　單機共同到期日問題可以簡單地描述如下：假設有n項具有相同的到期日的獨立工件，需經過單一機台的加工，工件加工途中不允許中斷（non-preemptive），當工件在到期日前完成，將產生提前成本；反之，當工件之完工時間大於共同到期日時，則會產生延遲成本，且不同的工件具有獨立且不對稱的提前及延遲權重。此排程問題之績效衡量準則為最小化加權提前及延遲成本（時間）。
　　由於上述問題已被證實為NP-hard之問題，使用最佳解法只能求解小規模之問題，若問題規模擴大，將會使得計算時間大幅增加，且不符效益，因此必須發展快速且有效的近似解法（approximation method），以期能在可接受的時間內求解規模較大之問題。而RBS演算法（recovering beam search algorithm）為近年被提出的一種能快速且兼顧品質的近似解法。
　　本研究應用並發展一套RBS演算法求解單機共同到期日問題。並透過標準題庫問題來測試所提出的演算法，實驗結果顯示本研究所提出的演算法可以有效求解到1000個工件數之問題。

In the single-machine scheduling problem with a common due date（CDD）, there are n jobs to be processed. No preemption is permitted. When a job is completed before its due date, it has earliness cost. Conversely, if a job is finished after the due date, it has tardiness cost. Each job has its own asymmetric early and tardy weight. The objective function is to minimize the total weighted earliness and tardiness.
This problem has been proven being NP-hard. Exact methods can only solve small instance problems. We must develop effective approximation methods to solve big instance problems. Recently proposed RBS （recovering beam search）algorithm is one of the effective approximation methods.
We propose a RBS algorithm for the single machine CDD problems. The proposed algorithm was examined through benchmark problems. Computational experiments show that the proposed RBS algorithm can deal with 1000 jobs problem and performs well.

誌謝　i
中文摘要　ii
英文摘要　iii
目 錄　iv
表目錄　vii
圖目錄　viii
第一章、導論　1
1.1研究動機與目的　1
1.2研究問題與限制條件　3
1.2.1研究問題　3
1.2.2假設與限制條件　5
1.3研究流程　7
1.4 論文架構　7
第二章、文獻探討　9
2.1共同到期日問題　9
2.2集束搜尋演算法　13
2.3RBS演算法　17
2.3.1原理　17
2.3.2演算法架構　20
第三章、研究方法　23
3.1過濾程序　23
3.2上界值　24
3.3下界值　28
3.3.1乘數調整法　30
3.4修復步驟　33
3.5 RBS求解 問題之演算流程　34
第四章、結果分析　36
4.1下界之績效評估　36
4.2參數選擇　38
4.3 RBS演算法之績效評估　40
4.3.1 RBS演算法與最佳解之比較　40
4.3.2 RBS演算法與啟發式演算法及鄰近搜尋法之比較　41
第五章、結論與建議　44
5.1結論　44
5.2未來研究方向與建議　45
參考文獻　46
附錄A 符號彙編　50
附錄B詳細測試結果　51

[1]Azizoglu, M. and Webster, S., (1997). “Scheduling job families about and unrestricted common due date on a single machine.” International Journal of Production Research, 35: 1321-1330.
[2]Baker, K.R. and Scudder, G.D., (1990) “Sequencing with earliness and tardiness penalties: A review.” Operations Research, 38: 22-36.
[3]Beraldi, P. and Ruszczyński, A., (2005). “Beam search heuristic to solve stochastic integer problems under probabilistic constraints.” European Journal of Operational Research, 167: 35-47.
[4]Biskup, D. and Feldmann, M., (2001). “Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates.” Computers & Operations Research, 28: 787-801.
[5]Blum, C., (2005). “Beam-ACO－hybridizing ant colony optimization with beam search: an application to open shop scheduling.” Computers & Operations Research, 35: 1565-1591.
[6]Cheng, T.C.E., (1990). “A note on a partial search algorithm for the single-machine optimal common due-date assignment and sequencing problem.” Computers & Operations Research, 17: 321-324.
[7]Cheng, T.C.E. and Gupta, M.C., (1989). “Suvey of scheduling research involving due date determination decisions.” European Journal of Operational Research, 38: 156-166.
[8]Cheng, T.C.E. and Kahlbacher, H.G., (1991). “A proof for the Longest-Job-First policy in one-machine scheduling.” Naval Research Logistics, 38: 715-720.
[9]De, P., Ghosh, J.B. and Wells, C.E., (1990). “Con due-date dtermination and sequencing.” Computers & Operations Research, 17: 333-342.
[10]De, P., Ghosh, J.B. and Wells, C.E., (1994). “Solving a generalized model for CON due date assignment and sequencing.” International Journal of Production Economics, 34: 179-185.
[11]Dileepan, P., (1993). “Common due date scheduling problem with separate earliness and tardiness penalties.” Computers & Operations Research, 20: 179-184.
[12]Della Croce, F., Ghirardi, M. and Tadei, R., (2002). “An improved branch-and-bound algorithm for the two machine total completion time flow shop problem.” Production, Manufacturing and Logistics, 139: 293-301.
[13]Della Croce, F., Ghirardi, M. and Tadei, R., (2004). “Recovering Beam Search: Enhancing the beam search approach for combinatorial optimization problems.” Journal of Heuristics, 10: 89-104.
[14]Della Croce, F., Narayan, V. and Tadei, R., (1996). “The two-machine total completion time flow shop problem.” European Journal of Operational Research, 90: 227-237.
[15]Della Croce, F. and T’kindt, V., (2002). “A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem.” Operational Research Society, 53: 1275-1280.
[16]Esteve, B., Aubijoux, C., Chartier, A. and T’kindt, V., (2006). “A recovering beam search algorithm for the single machine Just-In-Time scheduling problem.” European Journal of Operational Research, 172: 798-813.
[17]Feldmann, M. and Biskup, D., (2003). “Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches.” Computers & Industrial Engineering, 44: 307-323.
[18]Ghirardi, M. and Potts, C.N., (2005). “Makespan minimization for scheduling unrelated parallel machines: A recovering beam search approach.” European Journal of Operational Research, 165: 457-467
[19]Gordon, V., Proth, J.-M. and Chu, C., (2002). “A survey of the state-of-the-art of common due date assignment and scheduling research.” European Journal of Operational Research, 139: 1-25.
[20]Hall, N.G., Posner, M.E., (1991). “Earliness-tardiness scheduling problems, I: Weighted deviation of completion times about a common due date.” Operations Research, 39: 836-846.
[21]Hall, N.G., Kubiak, W. and Sethi, S.P., (1991). “Earliness-tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date.” Operations Research, 39: 847-856.
[22]Hao, Q., Yang, Z., Wang, D. and Li Z., (1996). “Common due-date determination and sequencing using tabu search.” Computers and Operations Research, 23: 409-417.
[23]Hino, C.M., Ronconi, D.P. and Mendes, A.B., (2005). “Minimizing earliness and tardiness penalties in a single-machine problem with a common due date.” European Journal of Operational Research, 160: 190-201.
[24]Hoogeveen, J.A., Oosterhout, H. and van de Velde, S.L., (1994). “New lower and upper bounds for scheduling around a small common due date.” Operations Research, 42: 102-110.
[25]Hoogeveen, J.A. and van de Velde, S.L., (1991). “Scheduling around a small common due date.” European Journal of Operational Research, 55: 237-242.
[26]Hoogeveen, J.A. and van de Velde, S.L., (1995). “Stronger Lagrangian bounds by use of slack variables: applications to machine scheduling problems.” Mathematical Programming, 70: 173-190.
[27]Kanet, J.J., (1981). “Minimizing the average deviation of job completion times about a common due date.” Naval Research Logistics Quarterly, 28: 643-651.
[28]Lauff, V. and Werner, F., (2004). “Scheduling with common due date earliness and tardiness penalties for multimachine problems: A survey.” Mathematical and Computer Modelling, 40: 637-655.
[29]Li, G., (1997). “Single machine earliness and tardiness scheduling.” European Journal of Operational Research, 96: 546-558.
[30]Liaw, C.-F., (1999). “A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem.” Computers & Operations Research, 26: 679-693.
[31]Lowerre, B.T., (1976). “The HARPY speech recognition system.” Ph.D. Thesis, Carnegie-Mellon University, USA.
[32]McMullen, P.R. and Tarasewich, P., (2005). “A beam search heuristic method for mixed-model scheduling with setups.” International Journal of Production Economics, 96: 273-283.
[33]Ow, P.S. and Morton, T.E., (1988). “Filtered beam search in scheduling.” International Journal of Production Research, 26: 35-62.
[34]Ow, P.S. and Morton, T.E., (1989). “The single machine early/tardy problem.” Management Science, 35: 177-191.
[35]Potts, C.N. and van Wassenhove, L.N., (1985). “A branch and bound algorithm for the total weighted tardiness problem.” Operations Research, 33: 363-377.
[36]Rubin, S., (1978). “The ARGOS image understanding system.” Ph.D. Thesis, Carnegie-Mellon University, USA.
[37]Sabuncuoglu, I. and Bayiz, M., (1999). “Job shop scheduling with beam search.” European Journal of Operational Research, 118: 390-412.
[38]Smith, W.E., (1956). “Various optimizers for single stage production.” Naval Research Logistics Quarterly, 3: 59-66.
[39]Szwarc, W., (1989). “Single-machine scheduling to minimize absolute deviation of completion times for a common due date.” Naval Research Logistics, 36: 663-673.
[40]Valente, J.M.S. and Alves, R.A.F.S., (2005). “Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time.” Computers & Industrial Engineering, 48: 363-375.
[41]Valente, J.M.S. and Alves, R.A.F.S., (2005). “Improved lower bounds for the early/tardy scheduling problem with no idle time.” Journal of the Operational Research Society, 56: 604-612.
[42]Van den Akker, M., Hoogeveen, H. and van de Velde, S., (2002). “Combining column generation and Lagrangean relaxation to solve a single-machine common due date problem.” INFORMS Journal on Computing, 14: 37-51.