現今平行機台環境較過去來得普及，機台數目亦是大幅增加，使得目前的製造系統不論在規模或複雜度上，對於生產管理與規劃兩方面均帶來更艱難的挑戰。如同絕大多數製造系統，整備亦為平行機台之生產前的必需步驟，但現有平行機台排程研究不論將是整備所造成時間與成本併入加工粗略地進行規劃，或是獨立考量以仔細評估其造成影響，大多都忽略了平行機台系統於實務上經常面對整備人力物力資源有限，短時間大量整備是否可行之限制，使得現場執行時未必能達成預期的生產線資源配置。倘若忽略此限制而貿然執行考慮未周全之排程規劃，當發生整備資源之競爭情形時，如何取捨或調度便無從依據，更難以確保原排程結果所提供之績效指標是否可靠，造成管理上的盲點。本研究針對等效平行機台在整備資源有限之狀況下，考慮機台的釋放時間(release time)、工件不同的整備與加工時間因素，以最小化延遲工件數為目標進行排程的規劃。並對此NP-hard問題進行分析後，利用不同的啟發式演算法如模擬退火法、基因演算法、以及禁忌搜尋法來加以求解，配合實際資料和模擬方式來比較演算法之間在求解品質與效率上的優劣，以提供整備資源有限之平行機台製造環境的決策管理者，一套有效且可信賴之決策方法。

Due to parallel machines have become more popular and the number of machines also increased largely in recent days, the scale and complexity of manufacturing systems today grew considerably and brought challenges to production management and planning. Similar to most manufacturing systems setup is also a necessary process to parallel machines, but parallel machine scheduling researches at present neglect the constraint that operators and resources for machine setup are limited that setup a number of machines in a short time is very likely infeasible, and consequently, the expected resource allocation is hardly to be performed. If a manager overlooked the constraint and executed an unconsidered schedule plan, when there was a lack of resources for setup he would have no idea how to allocate the limited setup resources and can not ensure whether he will reach the expected performance goal. This paper focuses on the scheduling problem of parallel machines systems with limited setup resources and considers unequal machine release time, job setup and process time to minimize total number of tardy jobs, and also introduces three meta-heuristics including simulated annealing, genetic algorithm and Tabu search to solve the problem, and finally compares the quality and efficiency of the solutions with simulated data referring real systems. The results of experiments provide managers an efficient and reliable way for decision making.

Allahverdi, A., J. N. D. Gupta, T. Aldowaisan. A review of scheduling research involving setup considerations, Omega, 27 219-239, 1999.
Balakrishnan, K., J. J. Kanet , S. V. Sridharan. Early/tardy scheduling with sequence dependent setups on uniform parallel machines, Computers & Operations Research, 26 127-141, 1999.
Bilge, mit, F. Kira, M. Kurtulan, P. Pekgn. A tabu search algorithm for parallel machine total tardiness problem, Computers & Operations Research 31 397-414, 2004.
Cao, D., M. Chen, G. Wan. Parallel machine selection and job scheduling to minimize machine cost and job tardiness, Computers & Operations Research, 32 1995-2012, 2005.
Cheng, R., M. Gen. Parallel machine scheduling problems using memetic algorithms, Computers & Industrial Engineering, 33 761-764, 1997.
Cochran, J. K., S-M Horng, J. W. Fowler. A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines, Computers & Operations Research, 30 1087-1102, 2003.
Franca, P. M., M. Gendreau, G. Laporte, F. M. Mller. A tabu search heuristic for the multiple processor scheduling problem with sequence dependent setup times, International Journal of Production Economics, 43 79-89, 1996.
Garey, M. R., D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
Gen, M., R. Cheng. Genetic Algorithm and Engineering Design, John Wiley & Sons, Inc. , 1997.
Gendreau, M., J-Y Potvin. Metaheuristics in combinatorial optimization, Annals of Operations Research, 140 189-213, 2005.
Graham, R. L., E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematic, 5 287-326, 1979.
Ho, Johnny C., Y-L Chang. Minimizing the number of tardy jobs for m parallel machines, European Journal of Operational Research, 84 343-355, 1995.
Kim, D-W, K-H Kim, W. Jang, F. F. Cheng. Unrelated parallel machine scheduling with setup times using simulated annealing, Robotics and Computer Integrated Manufacturing, 18 223-231, 2002.
Kim, D-W, D-G Na, F. F. Chen. Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective, Robotics and Computer Integrated Manufacturing, 19 173-181, 2003.
Lee, Y. H., M. Pinedo. Scheduling jobs on parallel machines with sequence-dependent setup times, European Journal of Operational Research, 100 464-474, 1997.
Lin, B. M. T., A. A. K. Jeng. Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs, International Journal of Production Economics, 91 121-134, 2004.
M’Hallah, Rym, R.L. Bulfin. Minimizing the weighted number of tardy jobs on parallel processors, European Journal of Operational Research, 160 471-484, 2005.
Min, L., W. Cheng. A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines, Artificial Intelligence in Engineering, 13 399-403, 1999.
Min, L., W. Cheng. Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems, Robotics and Computer-Integrated Manufacturing, 22 279-287, 2006.
Park, M-W, Y-D Kim. Search heuristics for a parallel machine problem with ready times and due dates, Computers & Industrial Engineering, 33 793-796, 1997.
Pinedo, M.. Scheduling, Prentice Hall, 1995.
Schutten, J. M. J., R. A. M. Leussink. Parallel machine scheduling with release dates, due dates and family setup times, International Journal of Production Economics, 46-47 119-125, 1996.
Sun, H., G. Wang. Parallel machine earliness and tardiness scheduling with proportional weights, Computers & Operations Research, 30 801-808, 2003.
Ser, G. A., F. Pico, A. Santiago. Identical machine scheduling to minimize the number of tardy jobs when lot-splitting is allowed, Computers & Industrial Engineering, 33 277-280, 1997.
Tandon, M., P. T. Cummings, M. D. Levan. Scheduling of multiple products on parallel units with tardiness penalties using simulated annealing, Computers and Chemical Engineering, 19 1069-1076, 1994.