臺灣博碩士論文加值系統

在電子商務的時代裡，由於全球化的競爭與市場環境變化快速，製造業的經營環境日益複雜，現在產品的生命週期短、交期短，顧客的需求亦變得多樣化。因此從前是大量化的生產，現在則轉變為量少樣多，客製化與彈性化的生產。無疑地，此種方式的轉變，使得工廠的生產線流程變更頻仍，生產排程的安排上，時程也不能夠太長，而且排程經常需要修正，以隨時應付顧客不同的需求，故重排程是企業在這個新時代裡不可缺少的生產管理功能。
重排程對生產現場而言，是極為複雜且不易處理的問題，傳統上都是以人工經驗來處理重排程問題，然而以人工經驗重排程的結果並不能確保是最好的排程結果，而且重排程的結果亦難以與ERP或MRP等電子化系統整合。而且現在訂單的型態變成量少樣多、交期短，生產型態的轉變成客製化、彈性化的訂單式生產，已經不再是單靠人工經驗就能夠處理重排程的問題，所以製造業目前普遍面臨了無法精確預估交期、缺乏快速回應顧客需求之能力。
本研究主要目的為探討製造業常常發生之重排程問題，並且提出一個可以即時處理製造業排程與重排程問題的基礎架構。在此架構中，先將排程與重排程問題中的變數與限制條件粹取出來，然後以本研究所發展的各種排程中斷事件處理程序，包括插單、抽單、變更交期、機器故障、備料不及與變更訂貨量，將問題表示成CSP(Constraint Satisfaction Problem)的形式，再應用各種 CSP相關的求解方法，如Search Algorithms、Constraint Propagation以及Variable and Value Ordering Heuristics，求解此排程或重排程問題。本研究最後則以Constraint Programming開發工具ILOG SOLVER、SCHEDULER，據此基礎架構實作一排程與重排程系統，並且以南台灣一家筆記型電腦組裝工廠為實例，測試處理排程與插單、抽單、變更交期與機器故障等重排程問題，結果顯示本研究所發展之排程與重排程基礎架構確實能夠有效地處理各種重排程問題。我們亦測試了兩種不同的演算法並且使用不同的重排程目標函式之重排程結果，這兩種演算法為Depth-First Backtracking Search以最小化makespan為重排程目標函式以及Schedule-or-Postponed以最小化change數量為重排程目標函式。

In the era of E-commerce, due to the global competition and rapid changes of markets, the management of manufacturing industries is much more complicated than before. Some distinct features of the present market environment are: shorter product-life, shorter production lead time, and smaller batches of production. The later demand has exerted great pressures on management for greater flexibility in production scheduling, which must meet the customer needs of rapid changing nature. Rescheduling is thus becoming an indispensable capability for modern production management, where activities of a production schedule, before it is completed, must be re-arranged due to requests of cancellation of orders, additions of urging orders, and/or changes of specifications of an existing order.

Rescheduling in the past was usually done manually, which requires expertise of experienced workers who, based on the previous cases, adjust activities and/or processes. However, the lack of systematic and optimal analysis is always an inherent problem of the solution approach that is based on personal experience. As a result, performance of production scheduling may not be efficient, and management may find it difficult to integrate the adjusted production scheduling into eBusiness system easily. Many manufacturing industries in Taiwan, who have no capability in systematic rescheduling, thus cannot predict exact due day for customers. The purpose of this research is to attempt to tackle the rescheduling problem by developing a systematic rescheduling framework for manufacturing industries.

We applied CSP (constraint satisfaction problem) as the solution tool to develop a CSP based scheduling and rescheduling framework for manufacturing industries. In the framework, scheduling or rescheduling problem is represented as a CSP model, which consists of processes for handling scheduling interruption events, including rush orders or order withdraws, work order changes, equipment breakdowns and due day changes. The model works in concert with CSP method such as Search Algorithms, Constraint Propagation and Variable/Value Ordering. The framework was applied to a simplified manufacturing environment of a notebook computer factory in southern Taiwan. We, based on the framework, develop a system using constraint programming tools ILOG Solver and Scheduler. The system is able to handle the scheduling interruption events efficiently and effectively. We also conducted experiments with two rescheduling methods, schedule-or-postponed with objective function of minimize-changes and depth-first backtracking search with objective function of minimize-makespan, and compared their results.

摘要I
ABSTRACTIII
誌謝V
目錄VI
表目錄VIII
圖目錄IX
壹、緒論1
一 研究背景1
二 研究動機2
三 研究目的4
四 研究範圍與限制5
(一)研究範圍5
(二)研究限制5
五 研究流程5
六 論文架構7
貳、文獻探討8
一 排程問題8
二 製造業排程特性分析10
三 Job-Shop Scheduling Problem11
(一) Job-Shop Scheduling問題的特性11
(二) Job-Shop Scheduling問題的相關排程技術11
四 重排程問題12
(一) 重排程因素14
(二) 重排程程序15
(三) 重排程決策17
(四) 重排程架構18
參、限制條件滿足問題(CSP)21
一 簡介21
二 CSP的定義22
三 CSP求解演算法22
(一) Search Algorithm22
(二) Constraint Propagation25
(三) Variable and Value Ordering32
四 Job Shop Constraint Satisfaction Problem35
五 Tools for Solving CSP36
肆、排程與重排程基礎架構38
一 簡介與名詞定義38
二 排程與重排程基礎架構39
三 初始排程階段41
(一)排程元素粹取41
(二)限制條件的轉換48
(三) CSP求解演算法模組57
四 重排程階段62
(一)排程中斷事件62
(二)重排程CSP模型之建立64
伍、系統實作75
一 系統架構75
二 系統實作79
三 系統評估86
(一)系統功能測試87
(二)不同重排程方法與重排程目標之測試91
(三)系統效能測試94
陸、結論與未來研究方向99
一 結論99
二 未來研究方向100
參考文獻101

1.吳鴻輝、李榮貴，1997，"生產排程之重排程決策問題的文獻探討與分析"，Journal of the Chinese Institute of Industrial Engineers, 14卷, 2期, 頁147-158。2.黃清雄，2000，"產業競爭力關鍵因素之研究--以台灣地區鋼線鋼纜業為例"，長榮管理學院經營管理研究所，碩士論文。3.楊家冠等，1995，"機械產業生產排程現況"，生產排程理論與實務技術研討會論文集，工研院機械所。4.楊家冠等，1995，"製造業生產排程問題剖析與對策"，機械工業雜誌，12月。5.陳建良，1995，"排程概述"，機械工業雜誌，12月。6.Abe, M., et al., 2000, "An Artificial Neural Network Optimized by a Genetic Algorithm for Real-time Flow-shop Scheduling"，Fourth International Conference on Knowledge-Based Intelligent Engineering Systems & Allied Technologies, 30 Aug-1, Brighton, UK, September7.Akturk, M. Selim, and Elif Gorgulu, 1999, "Match-up scheduling under a machine breakdown", European Journal of Operational Research, 112, pp.81-97.8.Allen, J. F., 1983, "Maintaining Knowledge about Temporal Intervals", Communications of the ACM, 11(26), pp.832-843.9.Baptiste, P., et al., 1995, "Constraint-Based Optimization and Approximation for Job-Shop Scheduling", In: Proceedings of the AAAI-SIGMAN Workshop on Intelligent Manufacturing Systems, Montreal, Canada10.Bartak, R., 1998, "Guide to Constraint Programming", http://ktilinux.ms.mff.cuni.cz/~bartak/constraints/intro.html11.Bean, James C., et al., 1991, "Matchup scheduling with multiple resources, release dates, and disruptions", Operation Research, Volume 39, Number 3, pp.470-48312.Brailsford, Sally C., et al., 1999, "Constraint Satisfaction Problems：Algorithms and Applications", European Journal of Operational Research, 119, pp.557-581.13.Brucker, P., et al., 1999, "Invited Review Resource-constrained project scheduling: Notation, classification, models, and methods", European Journal of Operational Research, 112, pp.3-4114.Brucker, P. and Knust, S., 2000, "A Linear Programming and Constraint Propagation-based Lower Bound for the RCPSP", European Journal of Operational Research, 127, pp.355-36215.Byeon, Eui-Seok, et al., 1998, "Decomposition Heuristics for Robust Job Shop Scheduling", IEEE Transactions on Robotics and Automation, Volume 14, Number 2, pp.303-31316.Cesta, A., et al., 2000, "A Constraint-Based for Project Scheduling with Time Windows", Technical Reports, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA17.Cheng, C. and Smith, S. F., 1994, "Generating Feasible Schedules under Complex Metric Constraints", In Proceedings of the Twelfth National Conference on Artificial Intelligence, Seattle, Washington.18.Cheng, C. and Smith, S. F., 1995, "Applying Constraint Satisfaction Techniques to Job Shop Scheduling", Technical Reports, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA19.Cheng, Y., 1999, "Arc Consistency Revisited", Information Processing Letters 70, pp. 175-184.20.Conway, R. W., et al., 1967, "Theory of Scheduling", Addison-Wesley21.Church, L. K., and Uasoy, R., 1992, "Analysis of Periodic and Event-driven Rescheduling Policies in Dynamic Shops", International Journal of Computer Integrated Manufacturing, 5, pp.153-16322.Daniels, R. L., and Kouvelis, P., 1995, "Robust Scheduling to Hedge against Processing Time Uncertainty in Single-stage Production", Management Science, Volume 41, Number 2, pp.363-376.23.Debruyne, R. and Bessiere, C., 2001, "Domain Filtering Consistencies", Journal of Artificial Intelligence Research, 14, pp.205-230.24.Dorndorf, U., et al., 2000, "Constraint Propagation Techniques for the Disjunctive Scheduling Problem", Artificial Intelligence, 122, pp.189-240.25.Dospisil, J. and Kendall, E., 2000, "Multimedia Authoring Framework with ILOG Solver", Computer Communications, 23, pp. 1484-1497.26.Eric Li, et al., 1996, "Flow-time Performance of Modified Scheduling Heuristics in a Dynamic Rescheduling Environment", Computers And Industrial Engineering (31) 1-2, pp.213-216.27.Fromherz, Markus, P.J., 2001, "Constraint-Based Scheduling", Proceedings of the American Control Conference Arlington, VA, June 25-27, pp.3231-324428.Graham, R.L., et al., 1979, "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey", Ann. Discrete Math, 5, pp.287-326.29.Gueret, C., et al., 2000, "Using Intelligent Backtracking to Improve Branch-and Bound Methods: An Application to Open-Shop Problems", European of Operational Research, 127, pp.344-354.30.Guo, B. and Nonaka, Y., 1999, "Rescheduling and Optimization of Schedules Considering Machine Failures", International Journal of Production Economics, pp.503-51331.Haralick, R. M., and Elliott, G. L., 1980, "Increasing Tree-search Efficiency for Constraint Satisfaction Problems", Artificial Intelligence, Vol. 14, No. 3, pp.263-313.32.Herrmann, J. W., 1999, "A Genetic Algorithm for Minimax Optimization Problems", Proceedings of the 1999 Congress on Evolutionary Computation, pp.1099-1103, Washington, D.C.33.Herrmann, J. W., 2001, "Improving Manufacturing System Performance through Rescheduling", Computer Integrated Manufacturing Laboratory, University of Maryland, June 2134.Hertz, A. and Widmer, M., 1996, "An improved tabu search approach for solving the job shop scheduling problem with tooling constraints", Discrete Applied Mathematics, 65, pp.319-345.35.Hirayama, K. and Yokoo, M., 2000, "An Approach to Over-Constrained Distributed Constraint Satisfaction Problems: Distributed Hierarchical Constraint Satisfaction", Proceedings of the Fourth International Conference on Multiagent Systems36.ILOG, 2000, "ILOG Scheduler 5.0 User''s Manual", V5.0, ILOG.37.Jain, A. S. and Meeran S., 1998, "A State-of-the-Art Review of Job-Shop Scheduling Techniques", Technical Report, Department of Applied Physics, Electronic and Mechanical Engineering University of Dundee, Dundee, Scotland, UK38.Johnson, L. A., and Montgomery, D. C., 1974, "Operations Research in Production Planning, Scheduling, and Inventory Control", Wiley, New York.39.Junker, U. and Nuijten, W., 1999, "Preference-based Search for Minimizing Changes in Rescheduling"，IJCIA-99，Stockholm，August 240.Kim, M. H., and Kim, Y.-D., 1994, "Simulation-based Real-time Scheduling in a Flexible Manufacturing System", Journal of Manufacturing Systems, 13, pp.85-93.41.Kumar, V., 1992, "Algorithms for Constraint-Satisfaction Problems: A Survey", AI Magazine, 13(1, Spring).42.Ladkin, P. B. and Maddux, R. D., 1989, "On Binary Constraint Networks", Technical Report, Kestrel Institute, Palo Alto, CA.43.Lai, R. and Hsu, P.-L. 2000, "A Constraint-Based Scheduler for the Job-Shop Scheduling Problem", Proceedings of the Chinese Institute of Industrial Engineers National Conference44.Le Pape, C., 1994, "Implementation of Resource Constraints in Ilog Schedule: a Library for the Development of Constraint-based Scheduling Systems", Intelligent Systems Engineering45.Leon, V. Jorge, et al., 1994, "Robustness Measures and Robust Scheduling for Job Shops", IIE Transactions, Volume 26, Number 5, pp.32-43.46.Shue L. -Y, and Li, S. -T, 2002, "A University Timetabling System with both Hard & Soft Constraints: A Case Study", Proceeding of International Conference on Pacific Rim Management 12th Annual Meeting, August 1-3, Los Angeles, USA, pp. 246-25247.Mehta, S.V., and Uzsoy, R. M., 1998, "Predictable Scheduling of a Job Shop Subject to Breakdowns", IEEE Transactions on Robotics and Automation, 14, pp.365-37848.Meiri, I., 1991, "Combining Qualitative and Quantitative Constraints in Temporal Reasoning", In Proceedings of the Ninth National Conference on Artificial Intelligence, Anaheim, CA., pp.260-267. 49.Miyashita, K., and Katia, S., 1994, "Adaptive Case-based Control of Schedule Revision", Morgan Kaufmann Publishers, San Francisco, pp.29-6650.Nonobe, K., and Ibaraki, T., 2001, "An Improved Tabu Search Method for the Weighted Constraint Satisfaction Problem", INFOR, 39, pp.131-15151.Nuijten, W.P.M. and Arts, E.H.L., 1996, "A Computational Study of Constraint Satisfaction for Multiple Capacitated Job Shop Scheduling", European Journal of Operational Research, 90, pp.269-284.52.Padmanabhuni, S., 1999, "Extended Analysis of Intelligent Backtracking Algorithms for the Maximal Constraint Satisfaction Problem", Proceedings of the IEEE Canadian Conference on Electrical and Computer Engineering Shaw Conference Center, Edmonton, Alberta, Canada May53.Parunak, H. V. D., 1991, "Characterizing the Manufacturing Scheduling Problem", Journal of Manufacturing Systems, 10, pp.241-259.54.Puget, J. -F, 1993, "Object Oriented Constraint Programming for Transportation Problems", The Institution of Electrical Engineers(待查)55.Puget, J. -F, 1994, "A C++ Implementation of CLP", Proceedings SPICIS''94.56.Sabuncuoglu, I., and Karabuk, S., 1999, "Rescheduling Frequency in an FMS with Uncertain Processing Times and Unreliable Machines", Journal of Manufacturing Systems, 18, 4, pp.268-283.57.Sadeh N., 1991, "Look-Ahead Techniques for Micro-Opportunistic Job Shop Scheduling", Ph.D. Thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA58.Sadeh, N., et al., 1995, "Backtracking techniques for the job shop scheduling constraint satisfaction problem", Artificial Intelligence, 76, pp.445-48059.Sadeh N. and Mark S. Fox, 1996, "Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem", Artificial Intelligence, 86, pp.1-41.60.Sally, C. Brailsford, et al., 1999, "Invited Review Constraint satisfaction problems: Algorithms and applications", European Journal of Operational Research, 119, pp.557-58161.Shafaei, R., and Brunn, P., 1999, "Workshop Scheduling Using Practical (Inaccurate) Data -Part 1: The Performance of Heuristic Scheduling Rules in a Dynamic Job Shop Environment Using a rolling Time Horizon Approach", International Journal of Production Research, 37, 17, pp.3919-392562.Shafaei, R., and Brunn, P., 1999, "Workshop Scheduling Using Practical (Inaccurate) Data -Part2: An Investigation of the Robustness of Scheduling Rules in a Dynamic and Stochastic Environment", International Journal of Production Research, 37, 18, pp.4105-4117.63.Smith, A. W., and Smith, B. M., 1997, "Constraint Programming Approaches to A Scheduling Problem in Steelmaking", in Proceedings of CP97 Workshop on Industrial Constraint-Directed Scheduling, Schloss Hagenberg, Austria, November. 64.Smith, Stephen F., 1994, "Reactive Scheduling System", Technical Reports, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA65.Tsang, E., 1993, "Foundations of Constraint Satisfaction", Harcourt Brace and Company66.Tsang, E. and Kwan, A., 1993, "Mapping Constraint Satisfaction Problems to Algorithms and Heuristics", Technical Report CSM254, Department of Computer Science, University of Essex, Colchester67.Vieira, G. E., et al., 2000, "Analytical Models to Predict the Performance of a Single-machine System under Periodic and Event-driven Rescheduling Strategies", International Journal of Production Research, Volume 38, Number 8, pp.1899-191568.Vieira, G. E., et al., 2000, "Predicting the Performance of Rescheduling Strategies for Parallel Machine Systems", International Journal of Production Research, Volume 19, Number 4, pp.256-266.69.Vieira, G. E., et al., 2002,"Rescheduling Manufacturing Systems: A Framework of Strategies, Policies, and Method", Journal of Scheduling, March 1470.Wallace, M., 1996, "Practical Applications of Constraint Programming", Journal of Constraints, 1(1 and 2), pp.139-168.71.Weil, G, et al., 1995, "Constraint Programming for Nurse Scheduling", IEEE Engineering in Medicine and Biology, pp. 417-42272.William, G., et al., 1998, "RTSS: An Interactive Decision Support System for Solving Real Time Scheduling Problems Considering Customer and Job Priorities with Schedule Interruptions", Computers & Operations Research, Vol. 25, No. 11, pp.981-995.73.Wu, S. David, et al., 1999, "A Graph-theoretic Decomposition of the Job Shop Scheduling Problem to Achieve Scheduling Robustness", Operations Research, Volume 47, Number 1, pp.113-12474.Yang, S. and Wang, D., 2000, "Constraint Satisfaction Adaptive Neural Network and Heuristics Combined Approaches for Generalized Job-Shop Scheduling", IEEE Transactions on Neural Networks, Vol. 11, No. 2, March, pp.474-486.