博碩士論文 954306002 詳細資訊


姓名 龔裕仁(Yu-jen Kung)  查詢紙本館藏   畢業系所 工業管理研究所在職專班
論文名稱 單機台相依置換時間之生產排程問題-以ITO透明導電薄膜產業為例
(A single machine scheduling problem with consideration of sequence-dependent setup time and multiple objectives)
檔案 [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 本研究主要為探討生產排程的相關理論與個案公司相關的產業環境,分析其在排程議題上的獨特性與適合的排程演算邏輯。個案公司的狀況為考量製程相依置換時間的確定性單機台多目標準則排程問題,影響排程績效的主要關鍵因素為製程相依的置換時間,在找出所有與置換時間相關的變數後提出對應的編碼準則以及求解公式,另外在條件限制的部分還需要考量原料抵達時間及原料保存期限,而排程的目標準則需要同時考量最大流程時間及總訂單交期延遲時間。本研究發現這兩個目標準則在排程結果中常是相互牽制的,且在現實的狀況中隨著公司營運目標及市場狀況的改變,會發生必須在這兩個目標之間作平衡取捨的情況。因此,在問題中求出單一的解是不符合實際需求的,企業經營者需要的資訊是排程的結果能夠明確的作為決策的依據,使其作出正確決策。
本研究以柏拉圖式的單機台多目標排程的模型架構並利用限制導引搜尋原則的啟發式演算法,建立適合個案公司的排程模型,其求解的過程為先建立單一目標的演算法則作為解的極限依據,再發展由其中一個目標為起點向另一個目標趨近的演算法則,使所有的可能解呈現明顯的負相關分佈。最後經由實驗結果證明,本研究發展的排程模型可以達到預期的效果並且有良好的求解品質,能成為提供解決個案公司或相關產業排程問題的方法,藉此改善並增加企業的利益。
摘要(英) This research mainly focuses on production scheduling related theories and analyze related industrial environment of case company. The objectives are to define suitable logic and to find out the special rules for case company. The most important characteristic in this case is the sequence-dependent setup time for production. We investigate and develop the solution and criterion for our case company. Moreover, we also consider the times of raw materials arrival and expiration date limit of raw materials stocked in this problem. The objectives need simultaneously consider Makespan and total tardiness. These two criteria are often mutually conflict in scheduling. The choice of criteria will depends on company’s business goal and market demand changed. Therefore, single solution for scheduling does not conform to the actual demand.
We use a deterministic model of single machine scheduling problem with consideration of sequence-dependent setup time and multiple objectives. We develop three special algorithms for case company and study their efficiency by experiment using the historical data. The first heuristic algorithm was based on simple dispatching rules of SST and SPT and try to find a near optimal makespan solution. The second heuristic is to find a near-optimal total tardiness solution based on simple dispatching rules of EDD, SST, and SPT. The last heuristic is to find a near Pareto-optimal solution by combining the first two algorithms. Our experimental results show that this model achieved our expectative and also has good solution quality. The algorithms we developed could be used to solve this kind of scheduling problem well and make contributions to enterprise’’s benefit.
關鍵字(中) ★ 最大流程時間
★ 總延遲時間
★ 製程相依置換時間
關鍵字(英) ★ Sequence-dependent setup time
★ Total tardiness
★ Makespan
論文目次 第 一 章: 緒論....1
第 二 章: 文獻探討 ....5
第 三 章: 個案公司排程問題分析.....26
第 四 章: 模型.....32
第 五 章: 啟發式演算法架構與建置.....48
第 六 章: 結論與未來研究方向......75
參考文獻.....78
附錄一 實驗結果的訂單置換時間列表......83
附錄二 實驗排程結果的各種細項列表......84
參考文獻 [1] Asano, M. and Ohta, H., “Single Machine Scheduling Using Dominance Relation to Minimize Earliness Subject to Ready and Due times,” International Journal of Production Research, Vol.44, pp.35-43 (1996).
[2] Baker, K.R., “Heuristic Procedures for Scheduling Job Families with Setups and Due Dates,” Naval Research Logistics, Vol.46, pp.978-991 (1999).
[3] Barnes, J.W. and Vanston, L.K., “Scheduling Jobs with Linear Delay Penalties and Sequence Dependent Setup Costs,” Operations Research, Vol.29, pp.146-160 (1981).
[4] Bianco, L., Ricciardelli, S., Rinaldi, G. and Sassano, A., “Scheduling Tasks with Sequence-Dependent Processing Times,” Naval Research Logistics, Vol.35, pp.177-184 (1988).
[5] Bruno, J. and Downey, P., “Complexity of Task Sequencing with Deadline, Setup Times and Changeover Costs,” SIAM Journal on Computing, Vol.7, pp.393-404 (1978).
[6] Burstall, R.M., “A Heuristic Method for a Job-Shop Scheduling Problem,” Operations Research, Vol.17, pp.291-304 (1966).
[7] Buzacott, J.A. and Dutta, S.K., “Sequencing Many Jobs on a Multi-Purpose Facility,” Naval Research Logistics Quarterly, Vol.18, pp.75-82 (1971).
[8] Conway, R.W., Maxwell, W.L. and Miller, L.W., Theory of Scheduling, Addison Wesley, Massachusetts, (1967).
[9] Driscoll, W.C. and Emmons, H., “Scheduling Production on One Machine with Changeover Costs,” IIE Transactions, Vol.9, pp.388-395 (1997).
[10] Farn, C.D. and Muhlemann, A.P., “The Dynamic Aspects of a Production Scheduling Problem,” International Journal of Production Research, Vol.17, pp.15-21 (1979).
[11] Feo, T.A., Sarathy, K. and McGahan, J., “A Grasp for Single Machine Scheduling with Sequence Dependent Setup Costs and Linear Delay Penalties,” Computers & Operations Research, Vol.23, pp.881-895 (1996).
[12] Gilmore, P.C. and Gomory, R.E., “Sequencing a One-state Variable Machine; A Solvable Case of the Traveling Salesman Problem,” Operations Research, Vol.12, pp.655-679 (1964).
[13] Glover, F., “Tabu Search-Part I,” ORSA Journal on Computing, Vol.1, pp.4-32 (1990).
[14] Glover, F., “Tabu Search-Part II,” ORSA Journal on Computing, Vol.2, pp.4-32 (1990).
[15] Haynes, R.D., Komar, C.A. and Byrd, J., “The Effectiveness of Three Heuristic Rules for Job Sequencing in a Single Production Facility,” Management Science, Vol.9, pp.575-580 (1973).
[16] He, W. and Kusiak, A., “Scheduling Manufacturing Systems,” Computers in Industry, Vol.20, pp.163-175 (1992).
[17] Holland, J.H., “Genetic Algorithms and the Optimal Allocation of Trials,” SIAM Journal on Computing, Vol.2, pp.99-105 (1973)
[18] Kaneko, E., Liquid Crystal Display, KTK Scientific, Tokyo, (1987).
[19] Kim, S.Y., Lee, Y.H. and Agnihotri, D., “A Hybrid Approach to Sequencing Jobs Using Heuristic Rules and Neural Networks,” Production Planning & Control, Vol.6, pp.445-454 (1995).
[20] Kirckpatrick, S., Gelatt, C.D. and Vecchi, M.P., “Optimization by Simulated Annealing,” Science, Vol.220, pp.671-689 (1983).
[21] Krajewski, L.J., et al. “Kanban, MRP, and shaping the manufacturing environment,” Manage Science, Vol.33, pp.39-57 (1987).
[22] Kusiak, A. and Finke, G., “Modeling and Solving the Flexible Forging Module Scheduling Problem,” Engineering Optimization, Vol.12, pp.1-12 (1987).
[23] Laguna, M., Barnes, J.W. and Glover, F.W., “Tabu Search Methods for a Single-Machine Scheduling Problem,” Journal of Intelligent Manufacturing, Vol.2, pp.63-74 (1991).
[24] Lawler, E.L., Lenstra, J.K., Rinnooy, K.A. And Shmoys, D.B., Sequencing and Scheduling: Algorithms and Complexity. In Logistics of Production a-nd Inventory, Amsterdam, Netherlands: North Holland, (1993).
[25] Lee, Y.H., Bhaskaran, K. and Pinedo, M., “A Heuristic to minimize the Total Weighted Tardiness with Sequence Dependent Setups,” IIE Transactions, Vol.29, pp.45-52 (1997).
[26] Lockett, A.G. and Muhlemann, A.P., “A Scheduling Problem Involving Sequence Dependent Changeover Costs,” Operations Research, Vol.20, pp.895-902 (1972).
[27] Monma, C.L. and Potts, C.N., “On the Complexity of Scheduling with Batch Setup Times,” Operations Research, Vol.37, pp.798-804 (1989).
[28] Moore, J.E., “An Algorithm for a Single-Machine Scheduling Problem with Sequence-Dependent Setup Times and Scheduling Windows,” IIE Transactions, Vol.7, pp.35-41 (1975).
[29] Ovacik, I.M. and Uzsoy, R., “Rolling Horizon Algorithms for a Single-Machine Dynamic Scheduling Problem with Sequence-Dependent Setup Times,” International Journal of Production Research, Vol.32, pp.1243-1263 (1994).
[30] Parker, R.G.., Deterministic Scheduling Theory, Chapman and Hall, London, (1995).
[31] Picard, J.C. and Queyranne, M., “The Time-Dependent Traveling Salesman Problem and its Application to The Tardiness Problem in One Machine Scheduling,” Operations Research, Vol.26, pp.86-110 (1978).
[32] Pinedo, M., Scheduling: Theory, algorithms, and systems, Prentice Hall, New Jersey, (1995).
[33] Rubin, P.A. and Ragatz, G.L., “Scheduling in a Sequence Dependent Setup Environment with Genetic Search,” Computers & operations research, Vol.22, pp.85-99 (1995).
[34] Sielken, R.L. Jr., “Sequencing with Set-up Costs by Zero-One Mixed Integer Linear Programming,” IIE Transactions, Vol.8, pp.369-371 (1976).
[35] Smith, W.E., “Various Optimizers for Single Stage Production,” Naval Research Logistics Quarterly, Vol.3, pp.59-66 (1956).
[36] Taha, H., “Sequencing by Implicit Ranking and Zero-One Polynomial Programming,” IIE Transactions, Vol.3, pp.299-301 (1971).
[37] Tan, K.C. and Narasimhan, R., “Multi-Objective Sequencing with Sequence Dependent Setup Times,” International Journal of Operations and Quantitative, Vol.3, pp.69-84 (1997).
[38] ten Kate, H.A., Wijngaard, J. and Zijm, W.H.M. “Minimizing Total Earliness, Tardiness, and Setup Costs,” School of Management and Organization, University of Groningen, Holland, Research Report No. RR, pp.1991-2012, (1991).
[39] Uzsoy, R., Martin-Vega, L.A., Lee, C.Y. and Leonard, P.A., “Production Scheduling Algorithms for a Semiconductor Test Facility,” IEEE transactions on semiconductor manufacturing, Vol.4, pp.270-280 (1991).
[40] Uzsoy, R., Lee, C. and Martin-Vega, A., “Scheduling Semiconductor Test Operations: Minimizing Maximum Lateness and Number of Tardy Jobs on a Single Machine,” Naval Research Logistics, Vol.39, pp.369-388 (1992).
[41] White, C.H. and Wilson, R.C., “Sequence Dependent Setup Times and Job Sequencing,” International Journal of Production Research, Vol.15, pp.191-202 (1977).
[42] Woodruff, D.L. and Spearman, M.L., “Sequencing and Batching for Two Classes of Job with Deadlines and Setup Times,” Production and Operations Management, Vol.1 pp.87-102 (1992).
[43] 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).
指導教授 葉英傑(Ying-chieh Yeh) 審核日期 2008-5-14

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡