單機台相依置換時間之生產排程問題-以ITO透明導電薄膜產業為例

本研究主要為探討生產排程的相關理論與個案公司相關的產業環境，分析其在排程議題上的獨特性與適合的排程演算邏輯。個案公司的狀況為考量製程相依置換時間的確定性單機台多目標準則排程問題，影響排程績效的主要關鍵因素為製程相依的置換時間，在找出所有與置換時間相關的變數後提出對應的編碼準則以及求解公式，另外在條件限制的部分還需要考量原料抵達時間及原料保存期限，而排程的目標準則需要同時考量最大流程時間及總訂單交期延遲時間。本研究發現這兩個目標準則在排程結果中常是相互牽制的，且在現實的狀況中隨著公司營運目標及市場狀況的改變，會發生必須在這兩個目標之間作平衡取捨的情況。因此，在問題中求出單一的解是不符合實際需求的，企業經營者需要的資訊是排程的結果能夠明確的作為決策的依據，使其作出正確決策。本研究以柏拉圖式的單機台多目標排程的模型架構並利用限制導引搜尋原則的啟發式演算法，建立適合個案公司的排程模型，其求解的過程為先建立單一目標的演算法則作為解的極限依據，再發展由其中一個目標為起點向另一個目標趨近的演算法則，使所有的可能解呈現明顯的負相關分佈。最後經由實驗結果證明，本研究發展的排程模型可以達到預期的效果並且有良好的求解品質，能成為提供解決個案公司或相關產業排程問題的方法，藉此改善並增加企業的利益。

關鍵字

最大流程時間；總延遲時間；製程相依置換時間

並列摘要

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] 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).

國際替代計量

單機台相依置換時間之生產排程問題-以ITO透明導電薄膜產業為例

未授權

主題瀏覽