圖形著色論於生產重排程之應用

Using Graph Coloring Techniques to Solve Rescheduling Problems in Production Plan

王文芊(Wen-Chien Wang)

指導教授 ： 陳以明

元智大學/工程學院/工業工程與管理學系/碩士(2011年)

摘要

排程問題是在探討如何將一群工件分配到有限資源，而在執行生產排程計畫過程中，遇到不可避免且必須重新調整之因素時，必須執行重排程(Rescheduling)。本研究探討發生緊急訂單事件時，須於時間視窗(time window)內進行局部重排。將重排程問題轉換成圖形著色問題(Graph Coloring Problem, GCP)，並利用圖形著色問題為核心，提出資源限制-深度優先搜尋 (Resource-Constraint Depth First Search, RC-DFS) 演算法結合深度優先搜尋(Depth First Search, DFS)與廣度優先搜尋(Breadth First Search, BFS)方法，分析既有資源及資源不足等條件之重排，並以變動性最小為目標及時間重疊之工件不得使用相同資源之限制，來解決緊急訂單重排程之問題。利用資源限制-深度優先搜尋演算法解決不同個案等問題，並將資源限制-深度優先搜尋演算法與啟發式演算法進行實驗比較。研究最後將重排程問題的圖形著色轉換與資源限制-深度優先搜尋演算法完成GCP支援決策系統之開發，提供生產決策者重排程評估與決策。

關鍵字

重排程 ； 圖形著色問題 ； 深度優先搜尋演算法 ； 廣度優先搜尋演算法

並列摘要

Scheduling is the process of deciding how to commit resources between varieties of possible tasks. In the process, decision maker will encounter the emergency events to reschedule the production planning. A rush order, for instance, is happened; we have to reschedule in the time window constraint. We convert rescheduling problem to Graph Coloring Problem, and we propose Resource-Constraint Depth First Search(RC-DFS) algorithm which combined the Depth First Search(DFS) and Breadth First Search(BFS) to solve the rescheduling if the rush order is happened. The proposed algorithm could find the more stable rescheduling and the variety of tasks with the overlapping the process time would not be allocated the same resource .We discuss the rescheduling if the rush order was happened in the existing resources and scarce resource. The performance of the proposed RC-DFS algorithm is compared with genetic algorithm. Tests have been carried out in which the GCP system to provide the decision makers to solve the problem of rescheduling.

並列關鍵字

Rescheduling ； Graph Coloring Problem ； Depth First Search ； Breadth First Search

參考文獻

林秋萍，「不同啟發式演算法應用於考量整備時間之單機排程問題之比較」，國

吳鴻輝、李榮貴，「生產排程之重排程決策問題的文獻探討與分析」，Journal of

陳亮宇，「一個針對分群問題的關係基因演算法之原理與應用」，國立中央大學

Bartak, R., “Guide to Constraint Programming”, (1998) ,

Brooks, R. L.“On colouring the nodes of a network”. Mathematical Proceedings of