大多數的排程模式均假定機器在所有的時程是可運轉的，但在實際的產業中，這種假設可能不是真的，例如需要一個預防性維修或機器發生故障等。在許多產業，機器故障是很普遍的，並且會造成工廠的活動很難預測，以致於降低了整體生產系統的效能。所以，如何安排維修來降低機器的故障率，已變成是決策者的共識。在本文中，我們著重於探討單機的故障與維修之排程問題，特別是以下所探討的三個相關問題：
1.根據我們所研習公司的經驗顯示，當機器經過一段長時間的運轉（即負載過重），提供一段較長的閒置時間是可以降低機器故障率的。這樣，我們就可發展一個啟發式演算法，來最大化總設置時間（或總閒置時間）。我們將採用分枝界限法來評估我們所提案的啟發式演算法。
2.在許多生產系統中，維修工作已被安排成規則性或定期性的工作。所以，我們需要發展排程的方法，來處理定期性維修系統。我們提出一個啟發式演算法，來解決非可續工件之排程問題，其目標是受限於定期性維修而求最小化最大延遲時間問題。我們將以工廠實際資料的計算結果，作為驗證啟發式演算法的效果。
3.在不同的維修情況下，我們發展了六種演算法，來改善我們研習公司所使用的最早交期時間法則。我們的問題是受限於需安排一個維修工作，來尋找一個最小化延誤工件數之排程。在本文中，我們將會顯示出六種演算法的改善率，實驗結果將作為檢驗各演算法的效果。

Most scheduling models assume that machines are available at all times. However, this assumption may not be true in real industrial settings. For example, a preventive maintenance activity is required or a machine breakdown occurs. In many industries, machine breakdowns are found prevalently and make the shop behavior hard to predict, and thereby reducing the efficiency of the production system. Therefore, how to schedule maintenance to reduce the breakdown rate has been recognized by the decision makers. In this thesis, we address the single machine scheduling problem with breakdown and maintenance. In particular, three related problems are discussed as follows:
1.Based on the experience of the studied company, a longer idle time can reduce the breakdown rate when machine is running without stopping for a long period of time (i.e. a heavy load). Thus, a heuristic is proposed to maximize the total setup time (or the total idle time). The proposed heuristic is evaluated by using the branch-and-bound algorithm.
2.In many manufacturing systems, maintenance has been scheduled regularly or periodically. Therefore, we need to develop scheduling method to deal with systems with periodic maintenance. A heuristic is proposed to solve the scheduling problem with nonresumable jobs. The objective is to minimize the maximum tardiness subject to periodic maintenance. Computational results based on real industrial data are provided to demonstrate the effectiveness of the heuristic.
3.Under different maintenance circumstances, we develop six algorithms to improve the EDD method used by the studied company. The problem under consideration is to find a schedule that minimizes the number of tardiness jobs subject to one maintenance. The improvement ratios of the six algorithms are shown in this thesis. Computational results are provided to demonstrate the effectiveness of the algorithms.

第一章 導論 1
1.1. 研究動機與研究目的 1
1.1.1. 研究動機 1
1.1.2. 研究目的 2
1.2. 研究範圍與步驟架構 3
1.2.1. 研究範圍與限制 3
1.2.2. 研究步驟與架構 4
第二章 相關之文獻探討 5
2.1. 前言 5
2.2. 有關機器故障的排程文獻 6
2.3. 有關機器維修的排程文獻 9
2.4. 其它研究領域的探討 13
第三章 機器在高故障率時之排程研究 14
3.1. 前言 14
3.2. 化纖工廠生產系統 16
3.3. 現行的排程方法 17
3.4. 啟發式演算法 17
3.4.1. 起始程序 18
3.4.2. 範例3.1. 20
3.4.3. 反覆程序 22
3.4.4. 範例3.2. 26
3.5. 分枝界限法 28
3.6. 計算結果 31
3.7. 結論 34
第四章 機器在定期維修時之排程研究 35
4.1. 前言 35
4.2. 符號及問題的設定 36
4.3. 啟發式演算法 37
4.4. 範例4.1. 42
4.5. 分枝界限法 44
4.6. 計算結果 47
4.7. 結論 48
第五章 機器在不定期維修時之排程研究 54
5.1. 前言 54
5.2. 排程問題 55
5.3. 現行的排程方法 56
5.4. 問題設定 56
5.5. 演算法A 57
5.6. 演算法B至F 58
5.7. 計算結果 63
5.8. 結論 65
第六章 結論與後續研究 67
6.1. 結論 67
6.2. 後續研究 69
參考文獻 71

林宏澤 (1989)「分枝界限法在流程工廠排程中之應用」，碩士論文，
國立台灣工業技術學院管理技術研究所工業管理學程。
Adiri, I., Bruno, J., Frostig, E. and Rinnooy Kan, A. H. G. (1989) Single machine flow-time scheduling with a single breakdown. Acta Informatica, 26, 679-696.
Adiri, I., Frostig, E. and Rinnooy Kan, A. H. G. (1991) Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs. Naval Research Logistics, 38, 261-271.
Akturk, M. S. and Gorgulu E. (1999) Match-up scheduling under a machine breakdown. European Journal of Operational Research, 112, 81-97.
Albers, S. and Schmidt, G. (2001) Scheduling with unexpected machine breakdowns. Discrete Applied Mathematics, 110, 85-89.
Alkhamis, T. M. and Yellen, J. (1995) Refinery units maintenance scheduling using integer programming. Applied Mathematical Modeling, 19, 543-549.
Allahverdi, A. (1995) Two-stage production scheduling with separated setup times and stochastic breakdowns. Journal of the Operational Research Society, 46, 896-904.
Allahverdi, A. (1996) Two-machine proportionate flowshop scheduling with breakdowns to minimize maximum lateness. Computers and Operations Research, 23, 909-916.
Allahverdi, A. (1999) Stochastically minimizing total flowtime in flowshops with no waiting space. European Journal of Operational Research, 113, 101-112.
Allahverdi, A. and Mittenthal, J. (1994a) Two-machine ordered flowshop scheduling under random breakdowns. Mathematical and Computer Modeling, 20, 9-17.
Allahverdi, A. and Mittenthal, J. (1994b) Scheduling on m parallel machines subject to random breakdowns to minimize expected mean flow time. Naval Research Logistics, 41, 677-682.
Allahverdi, A. and Mittenthal, J. (1995) Two-machine ordered flowshop scheduling under random breakdowns with a makespan objective function. European Journal of Operational Research, 81, 376-387.
Allahverdi, A. and Mittenthal, J. (1998) Dual criteria scheduling on a two-machine flowshop subject to random breakdown. International Transaction Operations Research, 5, 317-32.
Allahverdi, A. and Savsar, M. (2001) Stochastic proportionate scheduling with setups. Computers & Industrial Engineering, 39, 357-369.
Anily, S., Glass, C. A. and Hassin, R. (1998) The scheduling of maintenance service. Discrete Applied Mathematics, 82, 27-42.
Art, R. H. P. M., Knapp, G. M. and Lawrence, M. J. (1998) Some aspects of measuring maintenance performance in the process industry. Journal of Quality in Maintenance Engineering, 4, 6-11.
Asano, M. and Ohta, H. (1998) Scheduling with shutdowns and sequence dependent set-up times. International Journal of Production Research, 37, 1661-1676.
Birge, J. and Glazebrook, K. D. (1988) Assessing the effects of machine breakdowns in stochastic scheduling. Operations Research Letters, 7, 267-271.
Birge, J., Frenk, J. B. G. and Rinnooy Kan, A. H. G. (1990) Single-machine scheduling subject to stochastic breakdowns. Naval Research Logistics, 37, 661-667.
Cavory, G., Dupas, R. and Goncalves, G. (2001) A genetic approach to the scheduling of preventive maintenance tasks on a single product manufacturing production line. International Journal of Production Economics, 74, 135-146.
Chareonsuk, C., Nagarur, N. and Tabucanon, M. T. (1997) A multicriteria approach to the selection of preventive maintenance intervals. International Journal of Production Economics, 49, 55-64.
Chen, L. and Toyoda, L. (1991) Optimal generating units maintenance scheduling for multi-area system with network constraints. IEEE Transactions on Power Systems, 6, 1168-1174.
Chen, X. Q. T. and Tu, F. (1997) Scheduling the maintenance on a single machine, working paper, Department of Computer and System Science, Nankai University, Tianjin, People''s Republic of China.
Corder, A. S. (1976) Maintenance Management Techniques, McGraw-Hill, Maidenhead.
Deris, S., Omatu, S., Ohta, H., Shaharudin Kutar, L. C. and Samat, P. A. (1999) Ship maintenance scheduling by genetic algorithm and constraint-based reasoning. European Journal of Operational Research, 112, 489-502.
Dopazo, J. F. and Merrill, H. M. (1975) Optimal generator maintenance scheduling using integer programming. IEEE Transactions on Power Apparatus Systems, 5, 1537-1545.
Du, C. and Pinedo, M. (1995) A note on minimizing the expected makespan in flowshops. Naval Research Logistics, 42, 1251-1262.
Duffuaa, S. O. and Al-Sultan, K. S. (1999) A stochastic programming model for scheduling maintenance personnel. Applied Mathematical Modeling, 25, 385-397.
Dunn, R. L. (1988) Maintenance update 88. Plant Engineering, 42, 60-62.
Edwin, K. W. and Curtis, F. (1990) New maintenance scheduling method with production cost minimization via integer linear programming. Electrical Power and Energy Systems, 12, 165-170.
Egan, G. T., Dillon, T. S. and Morsztyn, K. (1976) An experimental method of determination of optimal maintenance schedules in power systems using the branch-and-bound technique. IEEE Transactions on Systems, Man and Cybernetics, 538-547.
Espinouse, M. L., Formanowicz, P. and Penz, B. (1999) Minimizing the makespan in the two-machine no-wait flow-shop with limited machine availability. Computers & Industrial Engineering, 37, 497-50.
French, S. (1982) Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Ellis Horwood, England.
Frosting, E. (1991) A note on stochastic scheduling on a single machine subject to breakdown-the preemptive repeat model. Probability in the Engineering and Informational Sciences, 5, 349-354.
Glassey, C. R. (1968) Minimum changeover scheduling of several products on one machine. Operations Research, 16, 342-352.
Glazebrook, K. D. (1984) Scheduling stochastic jobs on a single machine subject to breakdowns. Naval Research Logistics Quarterly, 31, 251-264.
Glazebrook, K. D. (1987) Evaluating the effects of machine breakdowns in stochastic scheduling problems. Naval Research Logistics Quarterly, 34, 319-335.
Glazebrook, K. D. (1991) On non-preemptive policies for stochastic single machine scheduling with breakdown. Probability in the Engineering and Informational Sciences, 5, 77-87.
Gopalakrishana, M., Mohan, S. and He, Z. (2001) A tabu search heuristic for preventive maintenance scheduling. Computers & Industrial Engineering, 40, 149-160.
Graham, J. H., Brockman, G. and Shea, J. (1995) Hybrid expert maintenance advisory system for naval systems applications. Naval Engineers Journal, 107, 23-32.
Graves, G. and Lee, C. Y. (1999) Scheduling maintenance and semiresumable jobs on a single machine. Naval Research Logistics, 46, 845-863.
Jacobs, F. R. and Bragg, D. J. (1988) Repetitive lots: flow-time reductions through sequencing and dynamic batch sizing. Decision Sciences, 19, 281-294.
Jing, C. and David, D. B. (1992) Flow shop scheduling in serial muti-product processes with transfer and set-up times. International Journal of Production Research, 30, 1819-1830.
Johnson, S. M. (1954) Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61-68.
Klein, R. and Scholl, A. (1996) Maximizing the production rate in simple assembly line balancing-A branch and bound procedure. European Journal of Operational Research, 91, 367-385.
Knodel, W. (1981) A bin packing algorithm with complexity O(nlogn) in the stochastic limit. Mathematical Foundations of Computer Science, 118, 369-378.
Kralj, B. and Petrovic, R. (1988) Optimal preventive maintenance scheduling of thermal generating units and power systems-A survey of problem formulation and solution method. European Journal of Operational Research, 35, 1-15.
Kralj, B. and Petrovic, R. (1995) A muti-objective optimization approach to thermal generating units maintenance scheduling. European Journal of Operational Research, 84, 481-493.
Kreimer, J. and Mehrez, A. (1994) Optimal data acquisition and processing by a multi-sever stand-by system. Operational Research, 42, 24-30.
Kubiak, W., Blazewicz, J., Formanowicz, P., Breit, J. and Schmidt, G. (2002) Two-machine flow shops with limited machine availability. European Journal of Operational Research, 136, 528-540.
Lee, C. Y. (1991) Parallel machines scheduling with non-simultaneous machine available time. Discrete Applied Mathematics, 30, 53-61.
Lee, C. Y. (1996) Machine scheduling with an availability constraint. Journal of Global Optimization, 9, 395-416.
Lee, C. Y. (1997) Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint. Operations Research Letters, 20, 129-139.
Lee, C. Y. and Liman, S. D. (1992) Single machine flow-time scheduling with scheduled maintenance. Acta Informatica, 29, 375-382.
Lee, C. Y. and Liman, S. D. (1993) Capacitated two-parallel machine scheduling to minimize sum of job completion time. Discrete Applied Mathematics, 41, 211-222.
Lee, C. Y., Lei, L. and Pinedo, M. (1997) Current trend in deterministic scheduling. Annals of Operations Research, 70, 1-42.
Lee, C. Y. and Chen, Z. L. (2000) Scheduling of jobs and maintenance activities on parallel machines. Naval Research Logistics, 47, 145-165.
Lee, C. Y. and Leon, J. (2001) Machine scheduling with a rate-modifying activity. European Journal of Operational Research, 128, 119-128.
Lee, C. Y. and Lin, C. S. (2001) Single-machine scheduling with maintenance and repair rate-modifying activities. European Journal of Operational Research, 135, 493-513.
Leon, V. J. and Wu, S. D. (1992) On scheduling ready-time, due-dates and vacations. Naval Research Logistics, 39, 53-65.
Liao, C. J. and Yu, W. C. (1996) Sequencing heuristics for dependent setups in a continuous process industry. Omega, 24, 649-659.
Liman, S. (1991) Scheduling with capacities and due-dates, Ph. D. Dissertation, Industrial and systems Engineering Department of Florida.
Liu, Z. and Sanlaville, E. (1995) Preemptive scheduling with variable profile precedence constraints and due dates. Discrete Applied Mathematics, 58, 253-280.
Mckone, K. E. and Weiss, E. N. (1998) TPM: planned and autonomous maintenance: bridging the gap between practice and research. Production and Operations Management, 7, 335-351.
Mehta, S. V. and Uzsoy, R. (1999) Predictable scheduling of a single machine subject to breakdowns. International Journal of Computer Integrated Manufacturing, 12, 15-38.
Mosheiov, G. (1994) Minimizing the sum of job completion times on capacitated parallel machines. Mathematical and Computer Modeling, 20, 91-99.
Mukerji, R., Merrill, H. M., Ericson, B. W., Parker, J. and Friedman, R. E. (1991) Power plant maintenance scheduling: Optimizing economics and reliability. IEEE Transactions on Power Systems, 6, 476-483.
Oliver, H. (1999) Scheduling in job shops with machine breakdowns: an experimental study. Computers & Industrial Engineering, 36, 137-162.
Percy, D. F. and Kobbacy, K. A. H. (2000) Determining economical maintenance intervals. International Journal of Production Economics, 67, 87-94.
Par, N. M. and Leigh, W. (1994) Maintenance scheduling: issues and results and research needs. International Journal of Operations and Production Management, 14, 47-69.
Pinedo, M. and Rammouz, E. (1988) A note on stochastic scheduling on a single machine subject to breakdown and repair. Probability in Engineering and Informational Sciences, 2, 41-49.
Ramudhin, A. and Ratliff, H. D. (1995) Generating daily production schedules in process industries. IIE Transactions, 27, 646-656.
Rishel, T. D. and Christy, D. P. (1996) Incorporating maintenance actives into production planning; integration at the master schedule versus material requirements level, International Journal of Production Research, 34, 421-446.
Roberts, S.M. and Escudero, L.F. (1983) Minimum problem-size formulation for the scheduling of plant maintenance personnel. Journal of Optimization Theory and Applications, 39, 345-362.
Sanlaville, E. (1995) Nearly on line scheduling of preemptive independent task. Discrete Applied Mathematics, 57, 229-241.
Sanlaville, E. and Schmidt, G. (1998) Machine scheduling with availability constraints. Acta Informatica, 35, 795-811.
Satoh, T. and Nara, K. (1991) Maintenance scheduling by using simulated annealing method. IEEE Transactions on Power Systems, 6, 850-857.
Schmidt, G. (1984) Scheduling on semi-identical processors. Zeitschrift fur Operations Research, 28, 153-162.
Schmidt, G. (1988) Scheduling independent tasks with deadlines on semi-identical processors. Journal of Operational Research Society, 39, 271-277.
Schmidt, G. (2000) Scheduling with limited machine availability. European Journal of Operational Research, 121, 1-15.
Selen, W. J. and Heuts, R. M. C. (1990) Operational production planning in a chemical manufacturing environment. European Journal of Operational Research, 45, 38-46.
Sherif, Y. S. and Smith, M. I. (1981) Optimal maintenance models for system subject to failure: a review, Naval Research Logistics Quarterly, 28, 47-74.
Sliva, E. L., Morozowski, M., Fonseoa, L. G. S., Oliveira, G. C., Melo, A. C. G. and Mello, J. C. O. (1995) Transmission constrained maintenance scheduling of generating units, a Stochastic Programming Approach. IEEE Transactions on Power Systems, 10, 695-701.
Smith, W. E. (1956) Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3, 59-66.
Stinson, J. P. and Smith, A. W. (1982) A heuristic programming for sequencing the static flowshop. International Journal of Production Research, 20, 753-764.
Sun, J. and Xue, D. (2001) A dynamic reactive scheduling mechanism for responding to changes of production orders and manufacturing resources. Computers in Industry, 46, 189-207.
Szwarc, W. and Gupta, J. N. D. (1987) A flow-shop problem with sequence-dependent additive setup times. Naval Research Logistics Quarterly, 34, 619-627.
Uskup, E. and Smith, S. B. (1975) A branch-and-bound algorithm for two-stage production-sequencing problem. Operations Research, 23, 118-136.
Vineyard, M. L. and Meredith, J. R. (1992) Effect of maintenance policies on FMS failures. International Journal of Production Research, 39, 2647-2657.
Wei, L. and Jinhua, C. (1995) Stochastic scheduling on a single machine subject to multiple breakdowns according to different probabilities. Operations Research Letters, 18, 81-91.
Yamayee, Z. A., Sidenbald, K. and Yoshimura, M. (1983) A computationally optimal maintenance scheduling method. IEEE Transactions on Power Apparatus Systems, 102, 330-338.