本研究探討多平行工作站環境中，訂單排程及可再用性資源之配置以使總延遲時間最小問題，並設定各訂單擁有不同可開工日（release date）及到期日。本研究提出以可開工日與到期日為基礎的分解解法，並結合基因演算法發展一個混合基因演算法（hybrid genetic algorithm；HGA）以求解此問題。為測試HGA的有效性，本研究測試五組小型問題、三組較大型問題，並將其結果與Lingo求得之最佳解及基本型基因演算法的求解結果進行比較。比較結果顯示本研究HGA在小型問題中的求解品質與Lingo解之最佳解差異在15％以內，並具備較基本型基因演算法更佳的穩定性。在大型問題中，HGA求解品質遠優於基本型基因演算法，顯示本研究所提方法可使用於大型平行工作站訂單排程與資源配置問題中。當基本型基因演算法使用分解解法所得之較佳品質的初解時（ 值為0），其求解品質亦出現大幅改善，顯示本研究之分解解法在初解品質的改善上確有效果。當比較不同的 值時， 值為0.1及0.2的求解結果優於其他 值的求解結果，顯示過高及過低的 比率皆會影響混合基因演算法的求解品質。最後，本研究以生產管理人員之決策過程為基礎，發展「決策支援基礎之模擬模型」，並將模擬結果與傳統排序方法進行比較，進而提供管理人員決策參考。結果顯示本研究之模擬模型可協助管理人員進行資源配置與訂單排程決策。

This study addresses a job scheduling and resource allocation (JSRA) problem with distinct release dates and due dates to minimize total tardiness in parallel work centers with a multi-processor environment. To solve the problem, this study proposes a hybrid genetic algorithm (HGA) with release and due date based decomposition heuristic. Five small-sized test problems are performed to evaluate the performance of the HGA, the pure GA (PGA), and the optimum solution obtained using Lingo 7.0. The results show that the percentage deviations between the HGA and Lingo are smaller than 15%, and the HGA has smaller variance than the PGA. Other three large-sized test problems are performed to evaluate the performance of the HGA and the PGA. Computational results show that the HGA performs well for large-sized problems. Additionally, comparing the computational results with those obtained using = 0, 0.1, …, 0.5, value between 0.1 and 0.2 have better solution quality. Finally, this study proposes a decision-supporting model, which integrates simulation, genetic algorithms and decision support tools, for solving the JSRA problem by practical perspective.

1. Ahmad, M.M., Dhafr, N., 2002, Establishing and improving manufacturing performance measures, Robotics and Computer Integrated Manufacturing, 18,171–176.
2. Aickelin, U., Dowsland, K.A., 2000, Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem, Journal of Scheduling, 3,:139–153.
3. Baesler, F.F., Sepulveda, J.A., 2006, Multi-objectives simulation optimization: a case study in healthcare management, International Journal of Industrial Engineering, 13(2), 156–165.
4. Bharadwaj, V., Ghose, D., Mani, V., Robertazzi, T.G., 1996, Scheduling divisible loads in parallel and distributed systems, IEEE Computer Society, New Jersey
5. Bock, D.B., Patterson, J.H., 1990, A comparison of due date setting, resource assignment, and job preemption heuristics for the multiproject scheduling problem, Decision Sciences, 21, 387–402.
6. Burke, E.K., Eware, R.F., Newall, J.P., 1998, Initialization strategies and diversity in evolutionary timetabling, Mathematics & Computation, 6, 81–103.
7. Chellapilla, K., 1998, Combining mutation operators in evolutionary programming, IEEE Transactins Evolutionary Computation, 2, 91–96.
8. Chen, Z.L., 2004, Simultaneous job scheduling and resource allocation on parallel Machines, Annals of Operations Research, 129, 135–153.
9. Cheng, T.C.E., Chen, Z.L., Li, C.L., 1996, Single-machine scheduling with trade-off between number of tardy jobs and resource allocation, Operations Research Letters, 19, 237–242.
10. Cheng, T.C.E., Janiak, A., Kovalyov, M.Y., 1998, Bicriterion single machine scheduling with resource dependent processing times, Journal on Optimization, 8(2), 617–630.
11. Cheng, T.C.E., Kovalyov, M.Y., Shakhlevich, N.V., 2006, Scheduling with controllable release dates and processing times: makespan minimization, European Journal of Operational Research, 175, 751–768.
12. Cheng, T.C.E., Kovalyov, M.Y., Shakhlevich, N.V., 2006, Scheduling with controllable release dates and processing times: total completion time minimization, European Journal of Operational Research, 175, 769–781.
13. Chu, P.C., Beasley, J.E., 1997, A genetic algorithm for the generalized assignment problem, Computers & Operations Research, 24, 17–23.
14. Daniels, R.L., Hoopes, B.J., Mazzola, J.B., 1996, Scheduling parallel manufacturing cells with resource flexibility, Management Science, 42, 1260–1276.
15. Daniels, R.L., Hua, S.Y., Webster, S., 1999, Heuristics for parallel-machine flexible-resource scheduling problems with unspecified job assignment, Computers & Operations Research, 26, 143–155.
16. Daniels, R.L., Mazzola, J.B., 1994, Flow shop scheduling with resource flexibility, Operations Research Society of America, 42, 504–522.
17. Daniels, R.L., 1990, A multi-objective approach to resource allocation in single machine scheduling, European Journal of Operational Research, 48, 226–241.
18. Davis, L., 1991, Handbook of genetic algorithms Van Nostrand Reinhold, New York
19. DeJong, K.A., Spears, W.M., 1990, An analysis of the interacting roles of population size and crossover in genetic algorithms, Proc First Workshop Parallel Problem Solving from Nature, Springer Verlag, Berlin, 38–47.
20. Engwall, M., Jerbrant, A., 2003, The resource allocation syndrome: the prime challenge of multi-project management, International journal of project management, 21, 403–409.
21. Gen, M., Sarif, A., 2005, Hybrid genetic algorithm for multi-time period production/distribution planning, Computers and Industrial Engineering, 48, 799–809.
22. Grefenstette, J.J., 1992, Optimization of control parameters for genetic algorithms. IEEE Transaction Systems, Mann & Cybernetics, 16, 122–128.
23. Guo, Z.X., Wong, W.K., Leung, S.Y.S., Fan, J.T., Chan, S.F., 2006, A genetic-algorithm-based optimization model for scheduling flexible assembly lines, International Journal of Advanced Manufacturing Technology, DOI 10.1007/s00170-006-0818-6.
24. Hu, G.H., Zhou, Z.D., Fang, H.C., 2006, A genetic algorithm for the inter-cell layout and material handling system design, International Journal of Advanced Manufacturing Technology, DOI 10.1007/s00170-006-0694-0.
25. Janiak, A., Kovalyov, M.Y., 1996, Single machine scheduling subject to deadlines and resource dependent processing times, European Journal of Operational Research, 94, 284–291.
26. Janiak, A., 1989, Minimization of the resource consumption under a given deadline in the two-processor flow-shop scheduling problem, Information Processing Letters, 32, 101–112.
27. Janiak, A.,1998, Minimization of the makespan in a two-machine problem under given resource constraints, European Journal of Operational Research, 107, 325–337.
28. Kaspi, M., Shabtay, D., 2004, Convex resource allocation for minimizing the makespan in a single machine with job release dates, Computers & Operations Research, 31, 1481–1489.
29. Kolisch, R., Padman, R., 2001, An intergraded survey of deterministic project scheduling, Omega, 29, 249–272.
30. Koulamas, C., Kyparisis, G.J., 2001, Single machine scheduling with release times, deadlines and tardiness objectives, European Journal of Operational Research, 133, 447–453.
31. Lee, Z.J., Lee, C.Y., 2005, A hybrid search algorithm with heuristics for resource allocation problem. Information Sciences, 173, 155–167.
32. Leong, G.K., Snyder, D.L., Ward, P.T., 1990, Research in the process and content of manufacturing strategy, Omega, 18, 109–122.
33. Li, C.L., 1995, Scheduling to minimize the total resource consumption with a constraint on the sum of completion times, European Journal of Operational Research 80, 381–388.
34. Maheswaran, R., Ponnambalam, S.G., 2003, An investigation on single machine total weighted tardiness scheduling problems, International Journal of Advanced Manufacturing Technology, 22, 243–248.
35. Mak, K.L., Wong, Y.S., 2000, Product grouping and resource allocation in multiline manufacturing systems, International Journal of Advanced Manufacturing Technology 16, 917–926.
36. Man, K.F., Tang, K.S., Kwong, S., 1999, Genetic Algorithms, Springer-Verlag London Limited, London.
37. Oguz, C., Ercan, M.F., 2005, A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks, Journal of Scheduling, 8, 323–351.
38. Oguz, C., Zinder, Y., Do, V.H., Janiak, A., 2004, Hybrid flow-shop scheduling problems with multiprocessor task systems, European Journal of Operational Research, 152, 115–131.
39. Peng, J.X., Li, K., Thompson, S., Wieringa, P.A., 2007, Distribution-based adaptive bounding genetic algorithm for continuous optimization problems, Applied Mathematics and Computation, 185, 1063–1077.
40. Pinedo, M., 2002, Scheduling: theory, algorithms, and systems, Prentice-Hall Englewood Cliffs, New Jersey.
41. Rabbani, M., Rahimi-Vahed, A., Torabi, S.A., 2007, Real options approach for a mixed-model assembly line sequencing problem, International Journal of Advanced Manufacturing Technology, DOI 10.1007/s00170-007-1058-0
42. Sadoun, B., 2000, Applied system simulation: a review study, Information Sciences, 124, 173–192.
43. Sampson, S.E., 2006, Optimization of volunteer labor assignments, Journal of Operatons Management, 24, 363–377.
44. Schutten, J.M.J., Leussink R.A.M., 1996, Parallel machine scheduling with release dates. due dates and family setup times, International Journal of Production Economics, 46, 119–125.
45. Shabtay, D., 2004, Single and two-resource allocation algorithms for minimizing the maximal lateness in a single machine, Computers & Operations Research, 31, 1303–1315.
46. Shabtay, D., Kaspi, M., 2006, Parallel machine scheduling with a convex resource consumption function, European Journal of Operational Research, 173, 92–107.
47. Shabtay, D., 2004, Single and two-resource allocation algorithms for minimizing the maximal lateness in a single machine, Computers & Operations Research, 31, 1303–1315.
48. Soremekun, G., Gurdal, Z., Haftka, R.T., Watson, L.T., 2001, Composite laminate design optimization by genetic algorithm with generalized elitist selection, Computer Structure, 79, 131–143.
49. Tompkins, J.A., White, J.A., Bozar, Y.A., Tanchoco, J.M.A., 2003, Facilities planning, 3rd edition, NJ, WILEY.
50. Tsai, T.I., 2007, A genetic algorithm for solving the single machine earliness/tardiness problem with distinct due dates and ready times, International Journal of Advanced Manufacturing Technology, 31, 994–1000.
51. Valente, J.M.S., Alves, R.A.F.S., 2005, An exact approach to early/tardy scheduling with release dates, Computers & Operations Research, 32, 2905–2917.
52. Van Wassenhove, L.N., Baker, K.R., 1982, A bicriterion approach to time/cost trade-offs in sequencing. European Journal of Operational Research, 11, 48–54.
53. Vickson, R.G., 1980, Two single machine sequencing problems involving controllable job processing times, AIIE transaction, 12, 258–262.
54. Watanabe, M., Ida, K., Gen, M., 2005, A genetic algorithm with modified crossover operator and search adaptation for the job-shop scheduling problem, Computers and Industrial Engineering , 48, 743–752.
55. Yang, K.K., Sum, C.C., 1993, A comparison of resource allocation and activity scheduling rules in a in a multiproject environment, Journal of Operatons Management, 11, 207–218.
56. Zhang, G.Q., Lai, K.K., 2006, Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem, European Journal of Operational Research, 169, 413–425.
57. 林基興，1997/04，遺傳演算法-有趣的人工智慧研究（三），科學月刊，0328（http://lib.khgs.tn.edu.tw/science/content/1997/00040328/0014.htm）