成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	蕭德芳 Shiau, Der-Fang
論文名稱：	成比例的彈性產流式生產排程最佳化問題之研究 Optimization of proportionate flexible flow shop scheduling problem
指導教授：	黃悅民 Huang, Yueh-Min
學位類別：	博士 Doctor
系所名稱：	工學院 - 工程科學系 Department of Engineering Science
論文出版年：	2008
畢業學年度：	96
語文別：	英文
論文頁數：	92
中文關鍵詞：	建構式基因演算法、建構啟發式、行產生法、總加權完成時間、平行機器排程、成比例產流式生產排程、禁忌搜尋法
外文關鍵詞：	Total weighted completion time, Constructive genetic algorithm, Proportionate flow shop, Constructive heuristic, Column generation, Parallel machine scheduling, Tabu search
相關次數：	點閱：167 下載：5
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

排序與排程在製造生產系統及資訊處理環境中扮演著重要的角色，而且也應用在不同的領域中。在生產排程的問題中，包括工作生產排程(job shop scheduling)、產流式生產排程(flow shop scheduling)、開放式生產排程(open shop scheduling)及混合式生產排程(mixed shop scheduling)，已有許多不同的方法發展出來解決複雜的排程問題。近年來人工智慧(artificial intelligence)搜尋技術，包括了類神經網路(neural network)、基因演算法(genetic algorithm)、禁忌搜尋(tabu search)、模擬退火(simulated annealing)及蟻群演算法(ant colony optimization)等方法有效的解決排程問題。這些方法大部分所找出的解趨向總體最佳解(global optimal)，而跳脫局部最佳解(local optimal)。另外行產生法(column generation)在文獻中已被證實有效的解決線性規劃問題，而且也已經成功的應用在不同的平行機器排程(parallel machine scheduling)問題。
在本論文中，主要是探討成比例彈性產流式生產排程問題(proportionate flexible flow shop, PFFS)。首先我們先討論成比例產流式生產排程問題(proportionate flow shop, PFS)，在這問題下，有一系列不同的機器是被安排在s個階層(stage)中，而且每一個階層包含單一機器。每個工作包括了s個操作程序(operations)，每個操作程序在機器上都需要一個處理時間，而且每個工作在不同的機器上的處理時間是相等。PFS的問題在近年來才吸引較多的注意力，並不像產流式生產排程(flow shop)在不同條件限制已有許多的文獻參考。PFFS問題結合了PFS的特性及平行機器排程問題 (也就是說在每一個階層存在多台相同的機器平行處理)。在本論文中，排程的目標函數(objective function)是找出最小總加權完成時間(total weighted completion time, TWCT)，然而在PFFS問題與平行機器排程問題中找出最小的TWCT，兩者之間有極顯著的不同；在平行機器排程最佳解中，單一機器上的工作(jobs)是依加權最短處理時間(weighted shortest processing time)法則進行排序，然而在PFFS問題找出最小的TWCT需要較複雜的方法才能得到最佳解。
本文中我們結合行產生法(column generation)與建構啟發式(constructive heuristic)方法有效的解決PFFS問題。首先，我們將PFFS問題公式化為一個限制的主要問題(restricted master problem, RMP)及包含一個集合分割的公式(set partitioning formulation)，而它的線性規劃寬鬆式是藉由行產生法來得到最佳解。再來，我們利用禁忌搜尋法搭配候選列表策略來產生在RMP所需的起始解。接下來，我們導出一個動態規劃演算法來解決單一機器的次問題(single-machine subproblem)。最後，當一個線性規劃寬鬆式完整解得到後(也就是說，當行產生法終止時)，我們利用了建構啟發式方法將單一機器上所排定的工作(jobs)做最佳化的排序。
然而，當工作數量和機器數目的比率高的時候，我們發現行產生法需要較長的時間得到最好的解；因此本論文提出另一個替代方法，稱為混合建構式基因演算法(hybrid constructive genetic algorithm, HCGA)，不僅解決了行產生法在工作數量和機器數目的比率高所需較長時間的問題，此外HCGA也可以有效的應用在其他平行機器排程上的問題。實驗模擬結果顯示行產生法與建構啟發式方法在合理的時間內得到最優的解，特別是當工作數量和機器數目的比率低的時候能在很短的時間內得到最優的解。另外實驗的結果也顯示混合建構式基因演算法在工作數量和機器數目的比率高的時候所需的時間優於行產生法。

Sequencing and scheduling describes a decision-making process that plays an important role in most manufacturing and production systems as well as in most information-processing environments. It also exists in many applications and most of them have demonstrated as NP complete. For the shop scheduling problems such as job shop, flow shop, open shop and mixed shop, many schemes are introduced to solve shop scheduling problem. There are several types of artificial intelligence (AI) search techniques in solving scheduling problems: neural networks (NN), genetic algorithm (GA), tabu search (TS), simulated annealing (SA) and ant colony optimization (ACO). Most AI search approaches try to find a better solution or escape from a local optimal to obtain the globally better solution. In recent times, column generation (CG) has proved an effective means of solving the linear relaxation programming involving huge set covering or set partitioning problems, and has been applied successfully to various parallel machine scheduling problems.
The studied scheduling problem is focused on the special case of the m machine flow shop problem, known as proportionate flow shop (PFS). In such a shop, a series of different machines is arranged in s stages (s > 1) with only a single machine at each stage. Each job consists of s sequential operations and each operation requires a processing time on machines and processing time for each job is equal on all machines. Unlike the flow shop scheduling problem under certain constraints that has attracted considerable attention, the PFS problems have recently gained considerable attention. Proportionate flexible flow shop (PFFS) scheduling problems combine the properties of proportionate flow shop scheduling problems and parallel machine scheduling problems (i.e., there are several identical machines in parallel at each stage). Minimizing the total weighted completion time in a PFFS problem significantly differs from the parallel-identical-machine scheduling problem, an optimal schedule in which the jobs on each machine are in weighted shortest processing time (WSPT) order. Thus, the PFFS problem of minimizing TWCT needs a more intricate approach.
In this study, a combined column generation and constructive heuristic (combined approach) is proposed to solve the PFFS problem with excellent quality solutions. First, the PFFS problem can be formulated into a restricted master problem (RMP) with a set partitioning formulation, whose linear relaxation is solved efficiently by a CG procedure. Moreover, to have an initial feasible RMP, a feasible schedule is generated, which is based on tabu search with a candidate list strategy. To solve single-machine subproblems, a dynamic programming algorithm is derived according to the optimality properties of a PFS problem. Finally, a constructive heuristic is employed for reconstructing jobs on a single machine to form an optimal sequence while an integral solution of the linear relaxation problem is obtained (i.e., when the CG procedure is terminated).
However, in situations involving that the ratio of the number of jobs to the number of machines is relatively high, the CG approach consumes considerable CPU time. Therefore, an alternative approach, named hybrid constructive genetic algorithm (HCGA), is also proposed in this dissertation to resolve the problem that the CG approach consumes much CPU time when the ratio of the number of jobs to the number of machines is relatively high. Furthermore, HCGA can be considered as another effective approach for other parallel machine scheduling problems. Simulation results demonstrate the effectiveness of the combined approach in obtaining excellent quality solutions in a reasonable time. In particular, the combined approach works extremely well when the ratio of the number of jobs to the number of machines is relatively small. Furthermore, experimental simulations also show that the HCGA approach consumes less computational time when the ratio of the number of jobs to the number of machines is relatively high.

TABLE OF CONTENTS
摘　要		I
Abstract		III
誌　謝		V
LIST OF TABLES		IX
LIST OF FIGURES		X
Chapter 1 Introduction		1
	1.1 The scheduling problem		1
	1.2 The job shop scheduling		2
	1.3 The flow shop scheduling		3
	1.4 The open shop scheduling		4	1.5 The mixed shop scheduling		5
	1.6 Organization of this dissertation		6
Chapter 2 The flexible flow shop scheduling problem		7
	2.1 Problem description and application area		7
	2.2 Solution approaches for FFS scheduling problems		9
	2.3 Genetic algorithms approach		10
	2.4 Tabu search approach		11
	2.5 Simulated annealing approach		13
	2.6 Ant colony optimization approach		14
	2.7 Column generation approach		16
Chapter 3 The proportionate flexible flow shop scheduling 
	Problem		18
	3.1 Proportionate flow shop		18
		3.1.1 Problem description and the merits and significance		18
		3.1.2 Literature review		19
	3.2 Proportionate flexible flow shop		20
Chapter 4 Combined column generation and constructive heuristic	22
	4.1 The properties of optimality		22
	4.2 Column generation approach		24
		4.2.1 The Restricted Master Problem (RMP)		24
		4.2.2 Single-machine subproblem		27
		4.2.3 Dynamic programming for the subproblem		28
		4.2.4 Branch-and-bound algorithm		31
	4.3 Reconstruction of the best schedule using constructive heuristic		34
Chapter 5 Hybrid constructive genetic algorithm		37
	5.1 Representation of structure and schema		38
	5.2 CGA modeling		41
		5.2.1 Tabu search		42
	5.3 The evolution process		43
		5.3.1 Initial population		44
		5.3.2 Selection and recombination operators		45
		5.3.3 Mutation operator		46
	5.4 The algorithm		46
Chapter 6 Experimental results		49
	6.1 Computational results using combined approach		49
		6.1.1 Experiment 1		49
		6.1.2 Experiment 2		51
6.2 Hybrid constructive genetic algorithm		53
			6.2.1 Experimental setup		53
6.3 Comparison and analysis of the combined approach and HCGA		54
6.4 Comparison of HCGA and pure tabu search		56
Chapter 7 Conclusions and future works		59
References		61
Appendix: Tabu search for generating an initial schedule in the 
initial RMP		72
自 述			76

LIST OF TABLES
Table 6.1 Computational results from the CG approach for problems with 
n = 20, 30, 30, 40, 50		51
Table 6.2 Computational results from the CG approach for problems with 
n = 60, 80, 100		52
Table 6.3 Comparisons of combined approach (CG+WSPT-MCI), HCGA and PTS for problems with n = 20, 30, 40 and 50		57
Table 6.4 Comparisons of HCGA, CG-PFFS and PTS for problems with 
n = 60, 80, 100		58	 

LIST OF FIGURES
Figure 2.1 An FFS scheduling problem with n jobs and three production stages	8	
Figure 2.2 Simulated annealing algorithm		14
Figure 2.3 ACS for TSP		16
Figure 4.1. Gantt chart for the example of the PFS problem in WSPT order		29
Figure 4.2. Gantt chart for the final sequence of the example		30
Figure 5.1. An example of three-machine schema		38
Figure 5.2. Framework of HCGA		48
                                    

1. P. Brucker, Y. N. Sotskov and F. Werner, Complexity of shop-scheduling problems with fixed number of jobs: a survey. Math Meth Oper Res, 65, 461–481, 2007.
2. M. L. Pinedo, Scheduling: Theory, algorithms, and systems. 2nd ed., Englewood Cliffs, NJ: Prentice-Hall, 2002.
3. R. Cheng, M. Gen and Y. Tsujimura, A tutorial survey of job shop scheduling problems using genetic algorithms, Part Ⅱ: Hybrid genetic search strategies. Computers & Industrial Engineering, 36, 343–364, 1999.
4. T. C. Chiang and L. C. Fu, Using dispatching rules for job shop scheduling with due date-based objectives. International Journal of Production Research, 45, 3245–3262, 2007.
5. M. S. Jayamonhan and C. Rajendran, New dispatching rules for shop scheduling: a step forward. International Journal of Production Research, 38, 563–586, 2000.
6. T. S. Raghu and C. Rajendran, An efficient dynamic dispatching rule for scheduling in a job shop. International Journal of Production Economics, 32, 301–313, 1993.
7. A. Baykasoglu, Linguistic-based meta-heuristic optimization model for flexible job shop scheduling. International Journal of Production Research, 40, 4523–4543, 2002.
8. Y. K. Kim, K. Park and J. Ko, A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling, Computers and Operations Research, 30, 1151–1171, 2003.
9. M. Garey, D. Johnson and R. Sethi, The complexity of flow shop and job shop scheduling. Mathematics Operations Research, 1, 117–129, 1976.
10. S. M. Johnson, Optimal two and three stage production schedules with setup time included. Naval Research and Logistics Quarterly, 1, 61–68, 1954.
11. C. R. Reeves, Genetic algorithm for flowshop scheduling problems. Computers and Operations Research, 15, 5–23, 1995.
12. I. H. Osman and C. N. Potts, Simulated annealing for permutation flow-shop scheduling. OMEGA, 17, 551–557, 1989.
13. F. A. Ogbu and D. K. Smith, The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem. Computers and Operations Research, 17, 243–253, 1989.
14. M. Ben-Daya and M. Al-Fawzan, A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, 109, 88–95, 1998.
15. H. G. Campbell, R. A. Dudek and M. L. Smith, A heuristic algorithm for n-job, m-machine sequencing problem. Management Science, 16/B, 630–637, 1970.
16. D. G. Dannenbring, An evaluation of flow-shop sequencing heuristics. Management Science, 23, 1174–1182, 1977.
17. J. N. D. Gupta, A functional heuristic algorithm for the flow-shop scheduling problem. Operational Reaerch Quarterly, 22, 39–47, 1971.
18. T. S. Hundal and J. Rajgopal, An extension of Palmer’s heuristic for the flow–shop scheduling problem. International Journal of Production Research, 26, 1119–1124, 1988.
19. M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness. San Francisco, CA: Freeman, 1979.
20. R. Linn and W. Zhang, Hybrid flow shop scheduling: a survey. Computers & Industrial Engineering, 37, 57–61, 1999.
21. W. Kubiak, C. Sriskandarajah and K. Zaras, A Note on the complexity of open shop scheduling problems. INFOR, 29, 284–294, 1991.
22. C. Y. Liu and R. L. Bulfin, Scheduling ordered open shops. Computers & Operations Research, 14, 257 – 264, 1987.
23. C. Prins, An overview of scheduling problems arising in satellite communications. Journal of the Operationl Research Society, 40, 611 – 623, 1994.
24. H. Brasel, T. Tautenhahn and F. Werner, Constructive heuristic algorithms for the open-shop problem. Computing, 51, 95–110, 1993.
25. C. Gueret, and C. Prins, Classical and new heuristics for the open-shop problem: A computational evaluation. European Journal of Operational Research, 107, 306–314, 1998.
26. D. Alcaide, J. Sicilia and D. Vigo, A tabu search algorithm for the open shop problem. Top, 5(2), 283–286, 1997.
27. C. F Liaw, A hybrid genetic algorithm for the open shop scheduling problem, European Journal of Operational Research, 124, 28 – 42, 2000.
28. P. Brucker, J. Hurink, B. Jurisch and B. Wostmann, A branch-and-bound algorithm for the open-shop problem. Discrete Applied Mathematics, 76, 43–59, 1997.
29. N. V. Shakhlevich, Y. N. Sotskov and F. Werner, Complexity of mixed shop scheduling problems: a survey. European Journal of Operational Research, 120, 343–351, 2000.
30. T. Masuda, H. Ishii and T. Nishida, The mixed shop scheduling problem. Discrete Applied Mathematics, 11 (2), 175–186, 1985.
31. T. Gonzalez and S. Sahni, Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery, 23 (4), 665–679, 1976.
32. C. Sriskandarajah and P. Ladet, Scheduling algorithms for flexible flowshops: worst and average case performance. European Journal of Operational Research, 43, 424–445, 1989.
33. A. Guint, M. M. Solomon, P. K. Kedia and A. Dussauchoy, A computational study of heuristics for two-stage flexible flowshops. International Journal of Production Research, 34, 1399–1416, 1996.
34. J. N. D. Gupta, A. M. A. Hariri and C. N. Potts, Scheduling a two-stage hybrid flow shop with parallel machines at the first stage. Annals of Operations Research, 69, 171–191, 1997.
35. C. Oğuz, M. Ercan, T. C. Edwin Cheng and Y. F. Fung, Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop. European Journal of Operational Research, 149, 390–403, 2003.
36. G. J. Kyparisis and C. Koulamas, A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines. European Journal of Operational Research, 182, 945–951, 2007.
37. A. Tozkapan, O. Kırca and C. S. Chung, A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem. Computers and Operations Research, 30(2), 309–320, 2003.
38. O. Moursli and Y. Pochet, A branch-and-bound algorithm for the hybrid flow shop. International Journal of Production Economics, 64, 113–125, 2000.
39. C. Oğuz, E. Fikret, T. C. Edwin Cheng and Y. F. Fung, Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop. European Journal of Operational Research, 149, 390–403, 2003.
40. G. Kyparisis and C. Koulamas, A note on makespan minimization in two-stage flexible flow shops with uniform machines. European Journal of Operational Research, In Press, 2005.
41. J. N. D. Gupta, K. Kruger, V. Lauff, F. Werner and Y. N. Sotskov, Heuristics for hybrid flow shops with controllable processing times and assignable due dates. Computers and Operations Research, 29(10), 1417–1439, 2002.
42. Y. Yang, S. Kreipl and M. Pinedo, Heuristics for minimizing total weighted tardiness in flexible flow shops. Journal of Scheduling, 3, 71–88, 2000.
43. L. X. Tang, H. Xuan and J. Liu, A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time. Computer Operations Reserach ,33, 3344–3359, 2006.
44. H. Wang, Flexible flow shop scheduling: optimum, heuristics and artificial intelligence solutions. Expert Systems, 22(2), 78–85, 2005.
45. J. H. Holland, Adaptation in natural and artificial systems. 1st edn, Massachusetts: MIT press, 1992.
46. Z. Michalewicz, Genetic Algorithms + Data structures = Evolution Programs. Third Edition, Springer, 13–44, 1999.
47. S. K. Iyer and B. Saxena, Improved genetic algorithm for the permutation flowshop scheduling problem. Computers and Operations Research, 31, 593–606, 2004.
48. I. Lee, R. Sikora and M. J. Shaw, A genetic algorithm based approach to flexible flow-line scheduling with variable lot sizes, IEEE Transactions on Systems, Man and Cybernetics, 27 (1), 36–54, 1997.
49. F. S. Şerifoğlu and G. Ulusoy, Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach. Journal of the Operational Research Society, 55(5), 504–512, 2004.
50. C. Oğuz and M. Ercan, A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Journal of Scheduling, 8(4), 323–351, 2005.
51. F. Glover, Tabu search – Part I. ORSA Journal of Computing, 1,190–206, 1989.
52. J. W. Barnes, M. Laguna, Solving the multiple-machine weighted flow time problem using tabu search. IIE Trans, 25,121–128, 1993.
53. U. Bilge, F. Kirac, M. Kurtulan and P. Pekgun, A tabu search algorithm for parallel machine total tardiness problem. Computers and Operations Research, 31, 397–414, 2004.
54. C. O.Kim, H. J. Shin, Scheduling jobs on parallel machines: a restricted tabu search approach. International Journal of Advanced Manufacturing Technology, 22, 278–287, 2003.
55. J. Dorn, M. Girsh, G. Skele and W. Slany, Comparison of iterative improvement techniques for schedule optimization. European Journal of Operational Research, 94, 349–361, 1996.
56. M. Ben-Daya, M. Al-Fawzan, A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, 109, 88–95, 1998.
57. E. Nowicki, The permutation with flow shop buffers: a tabu search approach. European Journal of Operational Research, 116, 205–219, 1999.
58. E. Taillard, Some efficient heuristic methods for flow-shop sequencing. European Journal of Operational Research, 47, 65–74, 1990.
59. E. Taillard, Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278–285, 1993.
60. E. Nowicki and C. Smutnicki, The flow shop with parallel machines: a tabu search approach. European Journal of Operational Research, 106, 226–253, 1998.
61. E. G. Negenman, Local search algorithms for the multiprocessor flow shop scheduling problem. European Journal of Operational Research, 128, 147–158, 1999.
62. B. Wardono and Y. Fathi, A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities. European Journal of Operational Research, 155, 380–401, 2004.
63. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller and E. Teller, Equation of State Calculations by Fast Computing Machines, J. of Chem. Phys., 21(6), 1087-1092, 1953.
64. P. J. M. Van Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory and Practice, Kluwer, 1987.
65. J. Teghem, D. Tuyttens and E. L. Ulungu, An interactive heuristic method for multi-objective combinatorial optimization, Computers and Operations Research, 27, 621–634, 2000.
66. D. T. Pham and D. Karaboga, Intelligent optimisation techniques: genetic algorithms, tabu search, simulated annealing and neural networks. London: Springer, 2000.
67. K. Steinhofel, A. Albrecht and C. K. Wong, Two simulated annealing-based heuristics for the job shop scheduling problem, European Journal of Operational Research, 118(3), 524–548, 1999.
68. J. H. Osman and C. N. Potts, Simulated annealing for permutation flow-shop scheduling. OMEGA, 17(6), 551–557, 1989.
69. F. A. Ogbu and D. K. Smith, The application of the simulated annealing algorithm to the solution of n/m/Cmax flowshop problem. Computers and Operations Research, 17(3), 243–253, 1990.
70. F. A. Ogbu and D. K. Smith, Simulated annealing for permutation flowshop scheduling. OMEGA, 19(1), 64–67, 1990.
71. I. Hisao, M. Shinta and T. Hideo, Modified Simulated annealing algorithms for the flow shop sequencing problem. European Journal of Operational Research, 81, 388–398, 1995.
72. C. Low, Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines. Computers & Operations Research, 32, 2013–2025, 2005.
73. V. Maniezzo and A. Carbonaro, Ant Colony Optimization: an Overview. Proceedings of MIC’99, III Metaheuristics International Conference, Brazil, 1999.
74. M. Dorigo and L. M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66, 1997.
75. M. D.Besten, T. Stutzle and M. Dorigo, Ant Colony Optimization for the Total Weighted Tardiness Problem. Lecture Notes in Computer Science, 1917, 611-620, 2000.
76. V. T'kindt, N. Monmarché, F. Tercinet and D. Laügt, An Ant Colony Optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. European Journal of Operational Research, 142(2), 250–257, 2002.
77. S. J. Shyu, B. M. T. Lin and P. Y. Yin, Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time. Computers & Industrial Engineering, 47, 181–193, 2004.
78. Y. Gajpal, C. Rajendran and H. Ziegler, An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs. European Journal of Operational Research, 155(2), 426–438, 2004.
79. C. Rajendran and H. Ziegler, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2), 426–438, 2004.
80. K. Alaykýran, O. Engin and A. Döyen, Using ant colony optimization to solve hybrid flow shop scheduling problems. International Journal of Advanced Manufacturing Technology, In press. DOI 10.1007/s00170-007-1048-2, 2007.
81. K. C. Ying and S. W. Lin, Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach. International Journal of Production Research, 44(16), 3161–3177, 2006.
82. T. Stützle and H. H. Hoos, MAX-MIN Ant system. Future Generation Computer Systems, 16(9), 889–914, 2000.
83. P. C. Gilmore and R. E. Gomory, A linear programming approach to cutting-stock problem. Operations Research, 9, 849-859, 1961.
84. P. H. Vance, C. Barnhart, E. L. Johnson and G. L. Nemhauser, Solving binary cutting stock problems by column generation and branch-and-bound. Computational Optimization and Applications, 3, 111-130, 1994.
85. M. Desrochers, J. Desrosiers and M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40, 342-354, 1992.
86. S. Lavoie, M. Minoux and E. Odier, A new approach for crew pairing problems by column generation with an application to air transport. European Journal of Operational Research. 35, 45-58, 1988.
87. A. Mehrotra and M. A. Trick, A column generation approach to graph coloring. Technical Report, Graduate school of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, 1993.
88. J. M. Van den Akker, J. A. Hoogeveen and S. L. Van De Velde, Parallel machine scheduling by column generation. Operations Research, 47, 862–872, 1999.
89. Z. L. Chen and W. B. Powell, Solving parallel machine scheduling problems by column generation. INFORMS Journal on Computing, 11(1), 78–94, 1999.
90. C. Y. Lee and Z. L. Chen, Scheduling jobs and maintenance activities on parallel machines. Nav Res Log, 47(2), 145–165, 2000.
91. J. M. Van den Akker, J. A. Hoogeveen and S. L. Van De Velde, Combining column generation and lagrangean relaxation to solve a single-machine common due date problem. INFORMS Journal on Computing, 14(1), 37–51, 2002.
92. P. S. Ow, Focused scheduling in proportionate flow shops. Management Science, 31, 852–869, 1985.
93. M. L. Pinedo, A note on stochastic shop models in which jobs have the same processing requirements on each machine. Management Science, 31, 840–845, (1985).
94. T. C. E. Cheng and N. Shakhlevich, Proportionate flow shop with controllable processing times. Journal of Scheduling, 2, 253–265, 1999.
95. S. S. Panwalkar, R. A. Dudek and M. L. Smith, Sequence research and the industrial scheduling problem. In S. E. Elmaghraby (ed.), Proc. Symp. on the theory of scheduling and its applications (pp. 29–37). Berlin/New York: Springer, 1973.
96. S. Hou and H. Hoogeveen, The three-machine proportionate flow shop problem with unequal machine speeds. Operations Research Letters, 31(3), 225–231, 2003.
97. A. Estevez-Fernandez, M. A. Mosquera, P. Borm and H. Hamers, Proportionate flow shop games. Tilburg University, Center for Economic Research, 2006.
98. N. V. Shakhlevich, H. Hoogeveen and M. L. Pinedo, Minimizing total weighted completion time in a proportionate flow shop. Journal of Scheduling, 1, 157–168, 1998.
99. A. Allahverdi, Two-machine proportionate flowshop scheduling with breakdowns to minimize maximum lateness. Computers and Operations Research, 23(10), 909–916, 1996.
100. A. Allahverdi and M. Savsar, Stochastic proportionate flowshop scheduling with setups. Computers & Industrial Engineering, 39(3), 357–369, 2001.
101. B. C. Choi, S. H. Yoon and S. J. Chung, Minimizing the total weighted completion time in a two-machne proportionate flow shop with different machine speeds. International Journal of Production Research, 44(4), 715–728, 2006.
102. B. C. Choi, S. H. Yoon and S. J. Chung, Minimizing maximum completion time in a proportionate flow shop with one machine of different speed. European Journal of Operational Research, 176(2), 964–974, 2007.
103. Y. P. Pan and L. Y. Shi, Dual constrained single machine sequencing to minimize total weighted completion Time. IEEE Transactions on Automation Science and Engineering, 2(4), 344–357, 2005.
104. W. E. Smith, Various optimizers for single-stage production. Nav Res Log Quart, 3, 59–66, 1956.
105. M. E. Lübbecke and J. Desrosiers, Selected topics in column generation. Operations Research, 53(6), 1007–1023, (2005).
106. John H. Holland, Building blocks, Cohort Genetic Algorithms, and Hyperplane-Defined Functions. Evolutionary Computation, 8(4), 373–391, 2000.
107. D. E. Goldberg, B. Korb and K. Deb, Messy genetic algorithm: Motivation, analysis, and first results. Complex Systems, 3, 493–530, 1989.
108. D. E. Goldberg, K. Deb, H. Kargupta and G. Harik, Rapid, accurate optimization of difficult problems using fast messy genetic algorithm. IlliGAL Rpt No. 93004, Illinois Genetic Algorithm Lab., Dept of General Engineering, University of Illinois, Urbana, 1993.
109. A. C. M. de Oliveira and L. A. N. Lorena, A constructive genetic algorithm for gate matrix layout problems. IEEE T Comput Aid, 21, 969–974, 2002.
110. L. A. N. Lorena and J. C. Furtado, Constructive genetic algorithm for clustering problems. Evolutionary Computation, 9(3), 309–327, 2001.
111. G. Ribeiro and L. A. N. Lorena, A constructive evolutionary approach to school timetabling. Lecture Notes in Computer Science, 2037, 130 –139, 2001.

校內：2008-12-25公開
校外：2008-12-25公開

簡易檢索 / 詳目顯示

相關論文