供應鏈管理之工廠規劃演算法

A Heuristic Factory Planning Algorithm for Supply Chain Management

孔令傑(Ling-Chieh Kung)

指導教授 ： 陳靜枝

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.00869

摘要

隨著商業活動日趨複雜，今日各企業必須與供應鏈內其他成員密切合作，以整合的方式追求供應鏈整體利益的最大化，才能提高自身競爭力與顧客滿意度，供應鏈管理也因此成為重要的研究課題。產生中長期、整合性的供應鏈規劃後，工廠必須更進一步產生短期、詳細的生產排程，才能配合整合性規劃。有別於不考慮順序的整合性規劃，工作間的先後順序影響短期生產排程的品質，使最佳化的困難度大幅提高。基於工廠規劃的重要性與困難度，本研究以工廠規劃問題的最佳化為研究目標。
本研究屬於先進規劃排程中之工廠規劃。主規劃產生供應鏈各成員中期的採購、生產與配銷計畫後，會對各工廠指定每期各商品的生產量，工廠規劃再依照產品結構、製造流程將各商品的需求轉換成工作。一個工作會被指定目標開始時間與目標結束時間，且含有多個階段；每個階段需要佔用特定工作站中任一機台若干時間，並且須在其先行階段產生足夠在製品後才能進行。因此，工廠規劃問題即為一複雜化之順序相關工作排程問題。
本研究對工廠規劃問題提出一多目標模型：最小化總延遲時間，最小化總流程時間，以及最小化總提前時間。工廠規劃問題雖可以混合整數規劃模型求得最佳解，但在規模龐大時，需要花費大量時間求解或完全無法求得解答，因此本研究提出ㄧ啟發性工廠規劃演算法，以求有效率地求得趨近最佳解之可行排程。
本啟發性工廠規劃演算法包含三階段：工作站排序、工作排序，以及工作排程。工作站排序會將工作站依工作負荷排序，以找出工廠中的瓶頸工作站。各工作依照其對瓶頸工作站的依賴度排序，依賴度愈高的工作優先權愈高。本研究提出一瓶頸導向排程演算法，完成工作排序後，將各工作依序排入工作行程。瓶頸導向排程演算法包含三個循環，第一循環將不切單下能不提前也不延後的工作排入，第二循環將切單後能不提前也不延後的工作排入，第三循環則將剩下的工作都排入。在排入一個工作的各階段時，皆以最小化此工作之流程時間的方式進行。
從三個角度出發的數值分析為本研究在時間與品質的成果提供佐證。情境分析包含十六種情境，交叉比較後能得出本研究適用的生產環境；效率分析證明本研究的求解時間和解品質與問題大小為線性關係；實例測試則驗證了本研究在實際製造產業中的可行性。這些數值分析顯示，本研究提出之工廠規劃演算法確實適於解決具一般性之工廠規劃問題。

關鍵字

供應鏈管理 ； 先進規劃排程 ； 多目標最佳化 ； 工廠規劃 ； 生產規劃排程 ； 啟發式演算法

並列摘要

In resent years, supply chain management (SCM) has become an emerging issue discussed widely. Each member involved in supply chain operations makes efforts to reduce its costs and maximize its profits. This study belongs to the Factory Planning (FP) level in Advanced Planning and Scheduling (APS), a supply chain planning model. After the Master Planning (MP) level completes a mid-term plan for members involved in supply chain operations, each manufacturer is assigned a production quantity for each product in each mid-term period. According to the product structure and routing of each product, the FP level models the production by designing jobs. Each job consists of several stages while each stage occupies several short-term periods at a specific work center and can start to work only after its preceding stages produce enough WIP. An FP problem is thus a generalized sequence-dependent job scheduling problem with its sequence-dependent nature make it an NP-hard problem and increases the difficulty of optimization. According to the importance and difficulty, this study focuses on optimizing scheduling problems inside factories.
FP problems discussed in this study have three objectives: minimizing delay time, minimizing cycle time, and minimizing advance time. Although FP problems can be formulated by an MIP model, the number of binary variables is too large for the MIP model to solve FP problems in an acceptable time. Therefore, this study develops a heuristic FP algorithm, Heuristic Factory Planning Algorithm (HFPA), to find a near-optimal solution.
HFPA contains three phases: work center sorting, job sorting, and job scheduling. HFPA first sorts work centers according to their work loads and finds the bottleneck work center. It then sorts jobs and gives higher priority to those jobs depending on the bottleneck work center more. After determining the order of jobs, the Bottleneck-Oriented Scheduling Algorithm (BOSA) is performed to schedule jobs one by one in three iterations. In the first iteration, it schedules jobs which can be scheduled in their preferred interval without splitting; in the second iteration, it schedules jobs which can be scheduled in their preferred interval with splitting; in the third iteration, it schedules all remaining jobs by advancing or delaying them. BOSA also minimize cycle time of this job when scheduling stages of a job.
HFPA can produce near-optimal or optimal solutions when the capacity is loose, the production type is flow shop, the bottleneck is significant, and the stage structure is complex. Each of the first three factors dominates the fourth factor and amplifies each other. However, comparing to the exponentially-growing solving time of exact algorithms such as MIP, HFPA is a polynomial time algorithm and requires only very less time to solve an FP problem. Therefore, HFPA can also perform well when the size of problem increases such that the solving time and the objective values do not grow exponentially. In conclusion, HFPA is suitable for solving general FP problems effectively and efficiently.

並列關鍵字

Supply Chain Management ； Advanced Planning and Scheduling ； Multi-objective Optimization ； Factory Planning ； Production Planning and Scheduling ； Heuristic Algorithm

參考文獻

[1] 吳宏祐，「先進規劃排程中考慮公平性與切單限制之主規劃排程演算法」，台灣大學資訊管理研究所碩士論文，民國94年。

[2] 林仲輝，「考慮共用料之供應鏈網路主規劃排程演算法」，台灣大學資訊管理研究所碩士論文，民國93年。

[4] 傅光宇，「供應鍊管理之主規劃排程演算法：考慮整備成本與時間對決策之影響」，台灣大學資訊管理研究所碩士論文，民國94年。

[5] 黃慨郁，「供應鍊網路中考量回收機制之主規劃排程演算法」，台灣大學資訊管理研究所碩士論文，民國95年。

[6] Azaieza, M.N. and S.S.A. Sharifb, “A 0-1 Goal Programming Model for Nurse Scheduling,” Computers and Operations Research, Vol. 32, pp. 491-507, 2005.