排程問題在許多領域中均可以見到，也有各種不同之方法已被提出來解決各種排程問題。多處理機之排程問題一般常用之解決方法有基因演算法、蟻群演算法與類神經網路等方法，這些方法均會在本論文中加以探討，並用以解決有資源限制之多處理機之工作排程問題。在本論文中，主要是探討多處理機排程問題，而且是有考慮工作在執行時有先後順序條件下，另外需使用各種不同資源，而這些資源是有限的。本論文中，不同之排程問題以各種不同之方法加以解決，其中基因演算法以解決不同工作型態間有安裝準備時間之排程問題，另外提出以類神經網路解決工作可搶先之排程方法，最後則是本文中提出一個基於蟻群演算法以解決在資源有限之條件下之多處理機排程問題。蟻群演算法具有快速收歛且執行速度快之特性中，已經被證實能有效解決各種排程問題，能有效避免如基因演算法執行時間過久之問題，也不會有類神經網路易於陷入局部最佳解之問題發生。在所提出之蟻群演算法中，除了提出針對問題之局部與全域更新法則外，另外提出兩個法則以解決多處理機之排程問題。其中動態法則是希望能從過去之較佳解中獲得適當之回饋，以有效提升排程之品質，因為在工作執行順序圖中，每一個工作之最早開工時間與最晚開工時間，是在無資源之條件下計算而得，但若考量資源與機器限制下，每一個工作之最早開工時間與最晚開工時間會變得極不實際，所以動態經驗法則即是設計來更新每一個工作之最晚開工時間，因為最晚開工時間會影響工作被選取之優先順序，若無法獲得正確之最晚開工時間，則蟻群演算法無法選出最適當之工作。另外延後機制經驗法則，則是讓某些工作延後執行以讓其他工作優先執行，則是用以產生所有可能之排程解，以避免陷入局部最佳解之問題。另外本文所提出之方法，所採用之費洛蒙架構，與傳統蟻群演算法之費洛蒙架構有極大之不同，是一個與時間相關之費洛蒙架構，當工作進行中若資源條件改變時，剩餘之工作亦能利用先前之費洛蒙值快速進行重排，無須進行重新學習。本文所提出之蟻群演算法方法加入所之設計相關法則，在各項模擬演算結果中顯示，確實能有效解決資源有限之條件下之多處理機排程問題，同時所提出之方法亦能有效計算出所須處理機之數量問題，另外亦能以解決專案排程之問題，專案排程之問題是資源有限之條件下之多處理機排程問題之ㄧ個特例，甚至此方法亦能應用於其他類似之問題，而且不需大幅修改排程系統

Scheduling problems have been extensively found in many applications and most of them have demonstrated as NP complete. Many schemes are introduced to solve scheduling problem. Some meta-heuristic methods to solve interested scheduling problems are presents and evaluates in this dissertation, such as simulated annealing (SA), genetic algorithm (GA), ant colony optimization (ACO) and Hopfield neural network (HNN) approaches. The studied scheduling problems are focus on the precedence and resource-constrained multiprocessor scheduling problems. Different scheduling problems are solved with different schemes. The genetic algorithm is used to solve the scheduling problems which have different type of job and different setup time between jobs. Additionally, the competitive Hopfield neural network (CHNN) is applied to solve real-time scheduling problems with resource constrained. Generally, GA was successfully used for similar problems in the past, and leading toward much more successful on some NP-complete domain than other algorithms. A GA generates a high quality of schedules in homogeneous or heterogeneous systems, but the required scheduling times are generally much higher than heuristic-based schemes. Many recent works indicate that ACO algorithm can work successfully in many different combinatorial problems. The ACO algorithm has been identified as an effective means of solving complex combinatorial optimization problems. A modified ant colony system is proposed to solve the scheduling problems with precedence and resource constrained. A two-dimensional matrix which has a time-dependency relation structure is used in this study to represent jobs on processors. Moreover, a dynamic rule is designed to modify the latest starting time of jobs and hence the heuristic function. Furthermore, a delay solution generation rule is proposed in this thesis to extend the exploration on the solution space, and is capable of escaping from the local optimal solution. Simulation results reveal that the proposed modified ant colony system algorithm provides an effective and efficient approach for solving multiprocessor system scheduling problems with resource constraints.

1. Cardeira, C., & Mammeri, Z. (1996). Neural network versus max-flow algorithms for multi-processor real-time scheduling. Real-Time Systems, Proceedings of the Eighth Euromicro Workshop, Page(s):175 – 180
2. S. Tzafestas, A. Triantafyllakis (1993), Deterministic scheduling in computing and manufacturing systems: a survey of models and algorithms. Mathematics and Computers in Simulation, 35(5), pp.397–434.
3. S. U. Seçkiner and M. Kurt (2007) , A simulated annealing approach to the solution of job rotation scheduling problems, Applied Mathematics and Computation, Volume 188, Issue 1, Pages 31-45
4. An integrated production planning and scheduling system for hybrid flowshop organizations International Journal of Production Economics, Volume 74, Issues 1-3, December 2001, Pages 33-48 F. Riane, A. Artiba and S. Iassinovski.
5. Merkle, D. Middendorf, M. & Schmeck, H. (2002). Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, Vol. 6, Issue: 4 On page(s): 333- 346
6. A hybrid genetic algorithm for the resource-constrained project scheduling problem
European Journal of Operational Research, In Press, Corrected Proof, Available online 25 January 2007,
Vicente Valls, Francisco Ballestín and Sacramento Quintanilla
7. Y. Z. Wang (2003), Using genetic algorithm methods to solve course scheduling problems, Expert Systems with Applications, Volume 25, Issue 1, Pages 39-50
8. T. Wang; X.-s. Zhou; Q.-r. Liu; Z.-y. Yang; Y.-l Wang (2006), An Adaptive Resource Scheduling Algorithm for Computational Grid,; Services Computing,. APSCC '06. IEEE Asia-Pacific Conference ,Page(s):447 – 450
9. Solving multi-objective production scheduling problems using metaheuristics European Journal of Operational Research, Volume 161, Issue 1, 16 February 2005, Pages 42-61
T. Loukil, J. Teghem and D. Tuyttens
10. Ruiz-Diaz F, French S. (1983), A survey of multi-objective combinatorial scheduling, Multi-objective decision making. New York, NY: Academic Press; p. 59–77.
11. P. Dileepan, T. Sen. (2000) , Bicriteria state scheduling research for a single machine, Omega;16:53-9.
12. T Murata, H Ishibuchi, H. Tanaka (1996), Multi-objective genetic algorithm and its applications to flowshop scheduling, Computer and Industrial Engineering, 30(4), pp.957–968.
13. A. Allahverdi (2003), The two- and m-machine flowshop scheduling problems with bicriteria of makespan and mean flow time. European Journal of Operational Research; 147(2), pp.373–396.
14. S. M. Lee and A. A. Asllani (2004), Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming, Omega, Volume 32, Issue 2, Pages 145-153.
15. Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The ant system: Optimization by a colony of cooperating agents. IEEE Transaction on System, Man and Cybernetics, 26(1): 1-13.
16. I. Ahmad and M.K. Dhodhi (1996), Multiprocessor Scheduling in a Genetic Paradigm, Parallel Computing, vol. 22, pp. 395-406,.
17. M.K. Dhodhi, I. Ahmad, and I. Ahmad, A Multiprocessor Scheduling Scheme Using Problem-Space Genetic Algorithms, Proc. IEEE Int’l Conf. Evolutionary Computation, pp. 214-219, 1995.
18. M. Yoo and M. Gen (2007), Scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm in heterogeneous multiprocessors system, Computers & Operations Research, Volume 34, Issue 10, Pages 3084-3098
19. W. Yao, J. You and B. Li (2004), Main sequences genetic scheduling for multiprocessor systems using task duplication, Microprocessors and Microsystems, Volume 28, Issue 2, Pages 85-94
20. H. Singh and A. Youseef (1996), Mapping and Scheduling Heterogeneous Task Graphs Using Genetic Algorithms, Proc. Heterogeneous Computing Workshop, pp.86-97.
21. P. Shroff, D. W. Watson, N.S. Flann, R. F. Freund (1996), Genetic Simulated Annealing for scheduling Data-Dependent Tasks in Heterogeneous environments, Proc. Heterogeneous Computing Workshop, pp. 98-104.
22. Liu, C., and Layland, J. (1973). Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of the ACM, 20 (l), pp. 46-61.
23. W. J. Gutjahr and M. S. Rauner (2007), An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria, Computers & Operations Research, Volume 34, Issue 3, Pages 642-666
24. Correa, R. C., Ferreira, A., & Rebreyend, P. (1996). Integrating list heuristics into genetic algorithms for multiprocessor scheduling. Parallel and Distributed Processing, Eighth IEEE Symposium. Page(s):462 – 469.
25. Hou, E. S. H., Ansari, N., & Ren, Hong. (1994). A genetic algorithm for multiprocessor scheduling. Systems. IEEE Transactions on Parallel and Distributed, Volume 5, Issue 2, Page(s):113 – 120
26. Correa, R. C., Ferreira, A., & Rebreyend, P. (1999). Scheduling multiprocessor tasks with genetic algorithms. IEEE Transactions on Parallel and Distributed Systems, Volume 10, Issue 8, Page(s):825 – 837
27. Zomaya, A. Y., Ward, C., & Macey, B. (1999). Genetic scheduling for parallel processor systems: comparative studies and performance issues. IEEE Transactions on Parallel and Distributed Systems, Volume 10, Issue 8, Page(s):795 – 812
28. Oh, J, & Wu, C. (2004). Genetic-algorithm-based real-time task scheduling with multiple goals. Journal of Systems and Software, Volume 71, Issue 3, Pages 245-258
29. Topcuoglu, H., Hariri, S., & Wu, M. Y. (2002). Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, Volume: 13, Issue: 3, pp. 260-274.
30. W. Xiao, P. Hao, S. Zhang, and X. Xu (2000), Hybrid flow shop scheduling using genetic algorithms, IEEE proceeding of 3rd world congress on intelligent control and automation, pp. 537–541.
31. Kwok, Y. K., Ahmad, I., & Gu, J. (1996). FAST: a low-complexity algorithm for efficient scheduling of DAGs on parallel processors. Parallel Processing, Proceedings of the 1996 International Conference, on Volume 2, Page(s):150 - 157 vol.2
32. Wu, M. Y., Shu, W., & Gu, J. (1997). Local search for DAG scheduling and task assignment. Parallel Processing, Proceedings of the 1997 International Conference, Page(s):174 – 180
33. I. Ferretti, S. Zanoni and L. Zavanella (2006), Production–inventory scheduling using Ant System metaheuristic, International Journal of Production Economics, Volume 104, Issue 2, Pages 317-326.
34. V. T'kindt, N. Monmarché, F. Tercinet and D. Laügt (2002), An Ant Colony Optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem, European Journal of Operational Research, Volume 142, Issue 2, 16 October 2002, Pages 250-257
35. S.J. Shyu, B.M.T. Lin and P.Y. Yin (2004), Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time,Computers & Industrial Engineering, Volume 47, Issues 2-3, November 2004, Pages 181-193.
36. Maniezzo, V. & Carbonaro, A. (1999). Ant Colony Optimization: an Overview. Proceedings of MIC’99, III Metaheuristics International Conference, Brazil
37. Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation; 1(1): 53-66.
38. Pierucci, P., Brandani, E. R., & Sogaro, A. (1996). An industrial application of an on-line data reconciliation and optimization problem. Computers & Chemical Engineering, Volume 20, Pages S1539-S1544.
39. Besten, M. D., Stützle, T. & Dorigo, M. (2000). Ant Colony Optimization for the Total Weighted Tardiness Problem. Berlin, Germany: Springer-Verlag, vol. 1917, Lecture Notes in Computer Science, pp. 611-620.
40. Gajpal, Y., Rajendran, C., & Ziegler, H. (2004). An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs. European Journal of Operational Research, Volume 155, Issue 2, Pages 426-438
41. Rajendran, C. & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, Volume 155, Issue 2, Pages 426-438
42. Stützle, T., Hoos, H. H. (2000). MAX-MIN Ant system. Future Generation Computer Systems, v.16 n.9, p.889-914.
43. Bauer, A., Bullnheimer, B., Hartl, R. F. & Strauss, C. (1999). An ant colony optimization approach for the single machine total tardiness problem. Proc. 1999 Congr. Evolutionary Computation, pp. 1445-1450.
44. Iredi,S., Merkle, D., & Middendorf, M. (2001). Bi-Criterion Optimization with Multi Colony Ant Algorithms. In First International Conference on Evolutionary Multi-Criterion Optimization (EMO’01)., vol. 1993, Lecture Notes in Computer Science, pp. 359–372. Springer-Verlag.
45. Merkle, D. & Middendorf, M. (2001). A new approach to solve permutation scheduling problems with ant colony optimization. Proceedings of the Evo. Workshops 2001, number 2037 in Lecture Notes in Computer Science, pages 484–494. Springer Verlag.
46. S. Yang and D. Wang (2000), Constraint satisfaction adaptive neural network and heuristics combined approaches for generalized, IEEE Transactions on. Neural Networks, vol. 11, pp. 474–486.
47. Hopfield, J. J., & Tank, D. W. (1985). Neural computation of decision in optimization problems. Biological Cybernetics, 52, 141-152.
48. Chen, R. M. & Huang, Y. M. (1998). Multiconstraint task scheduling in multiprocessor system by neural network. Proc. IEEE Tenth Int. Conf. on Tools with Artificial Intelligence, Taipei, pp. 288-294.
49. Chen, R. M. & Huang, Y. M. (2001). Competitive Neural Network to Solve Scheduling Problem. Neurocomputing, 37(1-4):177-196.
50. Huang, Y. M. & Chen, R. M. (1999). Scheduling multiprocessor job with resource and timing constraints using neural network. IEEE Trans. on System, Man and Cybernetics, part B, 29(4): 490-502.
51. R.M. Chen, S.T. Lo, and Y.M. Huang*, "Combining Competitive Scheme with Slack Neurons to Solve Real-Time Job Scheduling Problem", Expert Systems With Applications(in press), 33(1), Sept. 2007.
52. N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, E. Teller (1953), Equation of State Calculations by Fast Computing Machines, J. of Chem. Phys., Vol. 21, No. 6, pp. 1087-1092.
53. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi (1983), “Optimization by simulated annealing,” Science, vol. 220, pp. 671–680.
54. T. Loukil, J.Teghem and P. Fortemps (2007), A multi-objective production scheduling case study solved by simulated annealing, European Journal of Operational Research, Volume 179, Issue 3, Pages 709-722
55. K. Bouleimen and H. Lecocq (2003), A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version, European Journal of Operational Research, Volume 149, Issue 2, Pages 268-281
56. K. Steinhöfel, A. Albrecht and C. K. Wong (1999), Two simulated annealing-based heuristics for the job shop scheduling problem, European Journal of Operational Research, Volume 118, Issue 3, Pages 524-548
57. Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines
Computers & Operations Research, Volume 32, Issue 8, August 2005, Pages 2013-2025
Chinyao Low
58. J. Liu (1999), The impact of neighbourhood size on the process of simulated annealing: Computational experiments on the flowshop scheduling problem, Computers & Industrial Engineering, Volume 37, Issues 1-2, Pages 285-288
59. Brucker, P., Drexel, A., Möhring, R. H., Neumann, K., & Pesch, E. (1999). Resource-constraint project scheduling: Notation, classification, models, and methods. Eur. J. Oper. Res., vol. 112, no. 1, pp. 3–41.
60. Herroelen, W., B. Reyck, D. & Demeulemeester, E. (1998). Resource-constrained project scheduling: A survey of recent developments. Comput. Oper. Res., vol. 13, no. 4, pp. 279–302.
61. RM. Karp (1972), Reducibility among combinatorial problems: complexity of computer computations. NewYork: Plenum Press, pp. 85–103.
62. J.C. Ho, Y. L. Chang (1995), Minimizing the number of tardy jobs for m-parallel machines, European Journal of Operating Research, vol. 84, Pages343–55.
63. D.W. Kim, K. H. Kim, W. Jang and F. F. Chen (2002), Unrelated parallel machine scheduling with setup times using simulated annealing , Robotics and Computer-Integrated Manufacturing, Volume 18, Issues 3-4, Pages 223-231
64. K.R. Baker, G.D. Scudder (1990), Sequencing with earliness and tardiness penalties: A review, Operations Research; 38(1), pp.22–36.
65. Yalaoui, F., Chu, C. (2002). Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics, 76 (3), 265–279.
66. Du, J., Leung, J.Y.T. (1990), Minimizing total tardiness on one machine is NP-hard. Mathematics of Operational Research,15, pp.483–495.
67. Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P. (1977), Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, pp.343–362.
68. Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method
Robotics and Computer-Integrated Manufacturing, Volume 23, Issue 5, October 2007, Pages 503-516
Andrea Rossi and Gino Dini
69. M. H. Shenassa and M. Mahmoodi (2006), A novel intelligent method for task scheduling in multiprocessor systems using genetic algorithm, Journal of the Franklin Institute, Volume 343, Issues 4-5, Pages 361-371
70. C. Cardeira, Z. Mammeri (1997), Handling Precedence Constraints with Neural Network Based Real-time Scheduling Algorithms, Proceedings of Ninth Euromicro Workshop on Real-Time Systems, pp.207 –214.
71. G. A. Tagliarini, J. F. Christ, E. W. Page (1991), Optimization Using Neural Networks, IEEE Transaction on Computers, vol.40, no.12, pp.1347-1358.
72. J. J. Hopfield, D. W. Tank (1986), Computing with neural circuits: A model, Science, vol.233, pp. 625-633.
73. Y. Takefuji, K. C. Lee (1991), An artificial hystersis binary neuron: a model suppressing the oscillatory behaviors of neuron dynamics, Biological Cybernetics, vol.64, pp.353-356.
74. M. Takeda, J. W. Goodman (1986), Neural networks for computation: number representation and programming complexity”, Applied Optics, vol.25 pp.3033-3046.
75. M. Cohen , S. Grossberg (1983), Absolute stability of goal pattern formation and parallel memory storage by competitive neural networks, IEEE Trans. On System, Man, and Cybernetics, vol. 13, pp. 815-26.
76. C. J.Liao and H. C. Juan (2007), An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups, Computers & Operations Research, Volume 34, Issue 7, Pages 1899-1909
77. S.T. Lo, R.M. Chen, Y.M. Huang*, and C.L. Wu (2008), Multiprocessor System Scheduling with Precedence and Resource Constraints Using an Enhanced Ant Colony System, Expert Systems With Applications (in press), 35(4), 2008
78. Park, J. G., Park, J. M., Kim, D.S., Lee, C. H., Suh, S. W., & Han, M.S. (1994). Dynamic neural network with heuristic. IEEE Int. Conf. on Neural Networks, vol. 7, pp. 4650-4654.
79. S. C. Cheng, Y. M. Huang (2003), Scheduling Multi-Processor Tasks with Resource and Timing Constraints Using Genetic Algorithm, The 5th IEEE International Symposium on Computational Intelligence in Robotics and Automation, pp. 624-629.
80. C. N. Potts and L. N. VanWassenhove. Single machine tardiness sequencing heuristics. IIE Transactions, 23:346–354, 1991.
81. P. C. Chung, C. T. Tsai, E. L. Chen, Y. N. Sun (1994), Polygonal approximation using a competitive Hopfield neural network, Pattern Recognition, vol. 27, pp. 1505-1512.
82. Dirk C. Mattfeld and Christian Bierwirth (2000), An efficient genetic algorithm for job shop scheduling with tardiness objectives, European Journal of Operational Research, Volume 155, Issue 3, Pages 616-630.
83. B.T. Benjamin Khoo, Bharadwaj Veeravalli, Terence Hung and C.W. Simon See (2007), A multi-dimensional scheduling scheme in a Grid computing environment, Journal of Parallel and Distributed Computing, Volume 67, Issue 6, Pages 659-673