摘 要
生產排程是將生產系統中所使用的資源，做有效的配置與時程安排，是生產轉換過程中重要的決策與成敗關鍵。生產排程在實務應用上與排程理論上之差異，可進一步促進產學合作以利生產排程之研發與應用。本文著重於生產排程應用之實證研究，特別探討下列相關主題：
公司對生產排程的重視程度：永續經營是企業營運目標，獲利能力是其重要指標，若生產排程可以讓公司獲利能力提昇，經營者會較為重視生產排程，負責生產排程的管理層級也會較高。而公司現階段使用那些軟體應用在生產排程上，可了解先進生產排程與生產管理制度的應用現況。
生產系統製造型態：特定產品具有特定之生產途程，因應產品之生產途程與製造特性，故生產系統規畫出不同的生產型態。要了解公司之排程問題，就得先確定其生產型態，再進一步了解生產系統中各工作站或機器是否有特殊限制，包括機器設置時間、維修時間、工作移轉批量、暫存區大小等問題。
工作或訂單特性：不同客戶的訂單或不同的工作的重要性，經常被表示為優先處理因素，可以表示該工作在系統中的生產成本，或是該訂單的利潤；工作的處理時間與到期日的訂定方式；客戶訂單或工作若可事先預知到達生產系統的時間，是否會預先規畫在生產排程中；當某工作非常重要或急迫而進行插單，是否會強迫正在處理的工作先暫停，而優先處理該插單之工作。
生產排程時機與績效目標：公司排程的時機，以及績效目標及其重要性。本研究發現排程時機會影響績效目標並顯示其重要性。
以平行機生產排程探討工作與機器合適性之選擇，考量整備時間使總完工時間最小化，本研究對此問題發展三階段演算法，並利用分枝界限法評估其績效，且與非等效平行機之演算法進行評估。

ABSTRACT
Production scheduling, a method to allocate production resources into efficient and optimized priority, is the key factor for success when switching product items. This study probes into the difference between theoretical and practical applications of production scheduling, and promotes the future development and application in the context of optimal academic-industrial cooperation in terms of production scheduling. With empirical and primary studies, following topics are extendedly discussed in this paper.
Businesses’ extent of importance for production scheduling: Sustainability is the prime goal of the management, and the sole most important indicator to which would be the business profitability. If the performance of production scheduling is positively related to the profitability, there will more high-ranking managerial focus on scheduling and thereby promoting the corresponding profitability. Software appliances on production scheduling could provide a glance on one company’s production scheduling and production control system.
Production system type: Specific product requires different production routines. Therefore, production system needs to plan different production types accordingly. In order to comprehend one company’s scheduling issues, it is essential to determine its production type primarily, and then further study the special limitations of certain workshops or machines, such as machine setup times, maintenance, batch transfer, buffer zones, and etc.
Characteristics of job or order: The importance of job or order relative to the other jobs in the system often is denoted a priority factor. It may represent the cost of keeping the job in the system or the profit of the order. What is the setting method of job processing time and due date? As a job or order ready time is known in advance, it whether is subsumed to a planed schedule or not. As a job is very important or emergent, the scheduler whether is allowed to interrupt the processing job (preempt) at any point in time and put it on machine instead.
Goals of production scheduling: When does production scheduling be planned? What are the goals?
Production scheduling with parallel-machine and its choices of eligibility, and to consider setup times into the minimizing of total completion time. A three-stage heuristic and a branch-and-bound algorithm is proposed for this problem. We also evaluate the performance of the heuristic in comparison to a heuristic for unrelated parallel machines.

參考文獻
[1]Ahn, B.H. and Hyun, J.H., “Single facility multi-class job scheduling,” Computers and Operations Research, Vol.17, pp.265-272 (1990).
[2]Allahverdi, A., Gupta, J.N.D. and Aldowaisan, T., “A review of scheduling research involving setup considerations,” Omega, Vol.27, pp.219-239 (1999).
[3]Allahverdi, A., Ng, C.T., Cheng, T.C.E. and Kovalyov, M.Y., “A survey of scheduling problems with setup times or costs,” European Journal of Operational Research, Vol.187, pp.985-1032 (2008).
[4]Allaoui, H. and Artiba, A., “Integrating simulation and optimization to schedule a hybrid flow shop with maintentenance constraints,” Computers and Operations Research, Vol.47, pp.431-450 (2004).
[5]Allaoui, H. and Artiba, A., “Scheduling two-stage hybrid flow shop with availability constraints,” Computers and Operations Research, Vol.33, pp.1399-1419 (2006).
[6]Andres, C., Albarracin, J.M., Tormo, G., Vicens, E. and Garcia-Sabater, J.P., “Group technology in a hybrid flowshop environment: A case study,” European Journal of Operational Research, Vol.167, pp.272-281 (2005).
[7]Armentano, V.A. and Arroyo, J.E.C., “Genetic local search for multi-objective flowshop scheduling problems,” European Journal of Operational Research, Vol.167, pp.717-738 (2005).
[8]Asano, M. and Ohta, H., “Single machine scheduling using dominance relation to minimize earliness subject to ready and due times,” International Journal Production Economics, Vol.44, pp.35-43 (1996).
[9]Aytug, H., Lawley, M.A., McKay, K., Mohan, S. and Uzsoy, R., “Executing production schedules in the face of uncertainties: A review and some future directions,” European Journal of Operational Research, Vol.161, pp.86-110 (2005).
[10]Azizoglu, M. and Kirca, O., “Scheduling jobs on unrelated parallel machines to minimize regular total cost functions,” IIE Transactions, Vol.31, pp.153-159 (1999).
[11]Azizoglu, M. and Webster, S., “Scheduling parallel machines to minimize weighted flowtime with family set-up times,” International Journal of Production Research, Vol.41, pp.1199-1215 (2003).
[12]Baker, K.R. Introduction to Sequencing and Scheduling. Wiley, New York (1974).
[13]Blazewicz, J., Breit, J., Formanowicz, P., Kubiak, W. and Schmidt, G., “Heuristic algorithms for the two-machine flowshop with limited machine availability,” Omega, Vol.29, pp.599-608 (2001).
[14]Breit, J., “An improved approximation for two-machine flow shop scheduling with an availability constraint,” Information Processing Letters, Vol.90, pp.273-278 (2004).
[15]Buxey, G., “Production scheduling: practice and theory,” European Journal of Operational Research, 39, 17-31 (1989).
[16]Centeno, G. and Armacost, R.L., “Minimizing makespan on parallel machines with release time and machine eligibility restrictions,” International Journal of Production Research, Vol.42, pp.1243-1256 (2004).
[17]Centeno, G. and Armacost, R.L., “Parallel machine scheduling with release time and machine eligibility restrictions,” Computer and Industrial Engineering, Vol.33, pp.273-276 (1997).
[18]Chang, P.C., Chen, S.H. and Lin, K.L., “Two phase subpopulation genetic algorithm for parallel machine scheduling problem,” Expert Systems with Applications, Vol.29, pp.705-712 (2005).
[19]Chang, P.C., Chen, S.H., Fan, C.Y. and Chen, C.L., “Genetic algorithm integrated with artificial chromosomes for multi-objective flowshop scheduling problems,” Applied Mathematics and Computation, Vol.205, pp.550-561 (2008).
[20]Chang, P.C., Hsieh, J.C. and Wang, Y.W., “Genetic algorithms applied in BOPP film scheduling problems: Minimizing total absolute deviation and setup times,” Applied Soft Computing, Vol.3, pp.139-148 (2003).
[21]Chang, P.C., Wang, Y.W. and Liu, C.H., “New operators for faster convergence and better solution quality in modified genetic algorithm,” Lecture Notes in Computer Science, Vol.3611, pp.983-991 (2005).
[22]Chase, R.B. and Aquilano, N.J., “Production and Operations Management: A Life Cycle Approach”, 6th edu. Irwiu, Homewood, IL, p.5 (1992).
[23]Chase, R.B., “A classification and evaluation of research in operations management”, Journal of Operation Management, 1, 9-14 (1980).
[24]Chen, J.F. and Wu, T.H., “Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints,” Omega, Vol.34, pp.81-89 (2006).
[25]Cheng, T.C.E. and Sin, C.C.S., “A state-of-the-art review of parallel-machine scheduling research,” European Journal of Operational Research, Vol.47, pp.271-292 (1990).
[26]Cheng, T.C.E. and Wang, G., “An improved heuristic for two-machine flowshop scheduling with an availability constraint,” Operation Research Letters, Vol.26, pp.223-229 (2000).
[27]Cheng, T.C.E., Chen, Z.L. and Shakhlevich, N.V., “Common due date assignment and scheduling with ready times,” Computers & Operations Research, Vol.29, pp.1957-1967 (2002).
[28]Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T., “A Fast and Elitist Multi-Objective Genetic Algorithm-NSGA-II,” IEEE Transactions on Evolutionary Computation, Vol.6, pp.182-197 (2002).
[29]Dell’Amico, M. and Martello, S., “Bounds for the cardinality constrained P||Cmax problem,” Journal of Scheduling, Vol.4, pp.123-138 (2001).
[30]Dunstall, S. and Wirth, A., “A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines,” European Journal of Operational Research, Vol.167, pp.283-296 (2005a).
[31]Dunstall, S. and Wirth, A., “Heuristic methods for the identical parallel machine flowtime problem with set-up times,” Computers & Operations Research, Vol.32, pp.2479-2491 (2005b).
[32]Flynn, B.B., Sakakibara, S., Schroeder, R.G., Bates, K.A. and Flynn, E.J., “Empirical research methods in operations management,” Journal of Operations Management, 9, 250-279 (1990).
[33]Gendreau, M., Laporte, G. and Guimaraes, E.M., “A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times,” European Journal of Operational Research, Vol.133, pp.183-189 (2001).
[34]Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan., A.H.G., “Optimization and approximation in deterministic sequencing and scheduling: a survey,” Annals of Discrete Mathematics, 5, 287-326 (1979).
[35]Guo, Y., Lim, A., Rodrigues, B. and Yu, S., “Machine scheduling performance with maintenance and failure,” Mathematical and Computer Modelling, Vol.45, pp.1067-1080 (2007).
[36]Haouari, M., Hidri, L. and Gharbi, A., “Optimal scheduling of a two-stage hybrid flow shop,” Mathematical Methods of Operations Research, Vol.64, pp.107-124 (2006).
[37]Heady, R.B. and Zhu, Z., “Minimizing the sum of job earliness and tardiness in a multimachine system,” International Journal of Production Research, Vol.36, pp.1619-1632 (1998).
[38]Hwang, H.C., Chang, S.Y. and Lee, K., “Parallel machine scheduling under a grade of service provision,” Computer and Operations Research, Vol.31, pp.2055-2061 (2004).
[39]Ishibuchi, H. and Murata, T., “A multi-objective genetic local search algorithm and its application to flowshop scheduling,” IEEE Transactions on Systems, Man and Cybernetics–Part C: Applications and Reviews, Vol.28, pp.392-403 (1998).
[40]Kim, D.W., Kim, K.H., Jang, W. and Chen, F.F., “Unrelated parallel machine scheduling with setup times using simulated annealing,” Robotics and Computer-Integrated Manufacturing, Vol.18, pp.223-231 (2002).
[41]Laguna, M., “A heuristic for production scheduling and inventory control in the presence of sequence-dependent setup times,” IIE Transactions, Vol.31, pp.125-134 (1999).
[42]Lee, C.Y. and Vairaktarakis, G.L., “Minimizing makespan in hybrid flowshops,” Operational Research Letters, Vol.16, pp.149-158 (1994).
[43]Lee, C.Y., “Two-machine flowshop scheduling with availability constraints,” European Journal of Operational Research, Vol.114, pp.420-429 (1999).
[44]Li, Z. and Ierapetritou, M, “Process scheduling under uncertainty: Review and challenges,” Computers and Chemical Engineering, Vol.32, pp.715-727 (2008).
[45]Liao, C.J., Chen, C.M. and Lin, C.H., “Minimizing makespan for two parallel machines with job limit on each availability interval,” Journal of Operation Research Society, Vol.58, pp.938-947 (2007).
[46]Liao, L.M. and Tsai, C.H., “Heuristic algorithms for two-machine flowshop with availability constraints,” Computers and Industrial Engineering, Vol.56, pp.306-311 (2009).
[47]Lin, H.T. and Liao, C.J., “A case study in a two-stage hybrid flow shop with setup time and dedicated machines,” International Journal of Production Economics, Vol.86, pp.133-143 (2003).
[48]Malhotra, M. K. and Grover, V., “An assessment of survey research in POM: from constructs to theory,” Journal of Operations Management, 16, 407-425 (1998). [a13]
[49]Melnyk, S.A., Vickery, S.K. and Carter, P.L., “Scheduling, Sequencing, and Dispatching: Alternative Perspectives,” Production and Inventory Management, 2nd Quarter, 58-67 (1986).
[50]Meredith, J.R., Raturi, A., Amoako-Gbampah, K. and Kaplan, B., “Alternative research paradigms in operations,” Journal of Operations Management, 11, 239-256 (1989).
[51]Mokotoff, E., “Parallel machine scheduling problems: a survey,” Asia-Pacific Journal of Operational Research, Vol.18, pp.193-242 (2001).
[52]Monch, L., Zimmermannb, J. and Ottob, P., “Machine learning techniques for scheduling jobs with incompatible families and unequal ready times on parallel batch machines,” Engineering Applications of Artificial Intelligence, Vol.19, pp.235-245 (2006).
[53]Park, M.W. and Kim, Y.D., “Search heuristic for a parallel machine scheduling problem with ready times and due dates,” Computers and Industrial Engineering, Vol.33, pp.793-796 (1997).
[54]Pinedo, M., Scheduling: theory, algorithms and systems, 2nd ed., Prentice-Hall: Englewood Cliffs, New Jersey (2002).
[55]Pistikopoulos, E.N., “Uncertainty in process design and operations,” Computers & Chemical Engineering, Vol.19, pp.553-563 (1995).
[56]Psaraftis, H.N., “A dynamic programming approach for sequencing groups of identical jobs,” Operations Research, Vol.28, pp.1347-1359 (1980).
[57]Roseman, M.A. and J. S. Gero, “Reducing the Pareto optimal set in multi-criteria optimization with applications to Pareto optimal dynamic programming,” Engineering Optimization, Vol.8, pp.189-206 (1985).
[58]Salem, A., Anagnostopoulos, G.C. and Rabadi, G., “A branch-and-bound algorithm for parallel machine scheduling problems. Proceedings of the International Workshop on Harbour,” Maritime & Multimodal Logistics Modeling and Simulation, Society for Computers & Simulation International, Italy: Portofino, pp.88-93 (2000).
[59]Sanlaville, E. and Schmidt, G., “Machine scheduling with availability constraints,” Acta Informatica, Vol.35, pp.795-811 (1998).
[60]Schaller, J., Gupta, J.N.D. and Vakharia, A.J., “Scheduling a flowline manufacturing cell with sequence dependent family setup times,” European Journal of Operational Research, Vol.125, pp.324-339 (2000).
[61]Schmidt, C., “Scheduling with limited machine availability,” European Journal of Operational Research, Vol.121, pp.1-15 (2000).
[62]Shabtay, D. and Steiner, G., “A survey of scheduling with controllable processing times,” Discrete Applied Mathematics, Vol.155, No.13, pp.1643-1666 (2007).
[63]Stevenson, W. J., Operations Management, 8th ed., New York (2005).
[64]Suer, G.A., Vazquez, R. and Santos, J., “Evolutionary programming for minimizing the average flow time in the presence of non-zero ready times,” Computers and Industrial Engineering, Vol.45, pp.331-344 (2003).
[65]Swamidass, P.M. “Empirical science: New frontier in operations management research,” Academy of Management Review, 16, 793-814 (1991).
[66]T’kindt, V. and Billaut, J.C., “Multicriteria scheduling problems: a survey,” RAIRO Operations Research, Vol.35, pp.143-163 (2001).
[67]Vignier, A., Sonntag, B. and Portmann, M.C., “Hybrid method for a parallel-machine scheduling problem,” IEEE Symposium on Emerging Technologies and Factory Automation, ETFA 1, pp.671-678 (1999).
[68]Weng, M.X., Lu, J. and Ren, H., “Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective,” International Journal of Production Economics, Vol.70, pp.215-226 (2001).
[69]Wood, A. R. and Britney, R. R., “Production Operations Management: Research and teaching opportunities in the 1990s,” Operations Management Review, pp.7,33-42 (1988).
[70]Yang, W.H. and Liao, C.J., “Survey of scheduling research involving setup times,” International Journal of Systems Science, Vol.30, pp.143-155 (1999).
[71]Yi, Y., and Wang, D.W., “Soft computing for scheduling with batch setup times and earliness–tardiness penalties on parallel machines,” Journal of Intelligent Manufacturing, Vol.14, pp.311-322 (2003).
[72]Zhu, Z. and Heady, R.B., “Minimizing the sum of earliness/tardiness in multi-machine scheduling: A mixed integer programming approach,” Computers & Industrial Engineering, Vol.38, pp.297-305 (2000).
[73]黃俊英，企業研究方法，台灣東華書局，民國90年3月，頁43-44。