蟻群演算法於線上排程問題之研究

Ant Colony Optimization for On-line Scheduling Problem

詹莊龍(Chuang-Lung Chan)

指導教授 ： 梁韵嘉

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

https://doi.org/10.6838/YZU.2008.00199

摘要

現今製造環境下，多數產品開始隨著顧客需求做客製化修改與功能變動，同時慢慢導入顧客分級化制度，所以企業重要的訂單更不能接受產品延遲的狀況，以避免造成顧客忠誠下降與訂單流失，導致信譽受損；且顧客產品亦不可以太早完工，過早完工的產品須仰賴倉儲存放，造成企業需要大型倉儲空間以及管理員工等成本項目的使用，基於以上種種原因，本研究欲利用蟻群演算法 (Ant Colony Optimization; ACO) 找尋訂單完工與顧客交期的平衡點，以避免產品過早或延遲的現象發生，並考量線上生產環境，期望找尋交期時間下獲得近似完工時間之最佳結果。於是在研究過中利用所提出的蟻群最佳化演算法，應用於單一機台線上排程問題及流程型多機線上排程問題兩方面，分別使用不同交期指派策略於各生產型態上，測試不同的生產狀況，包含工單數為100、500與2500三種，應用於間隔到達時間與操作時間組合三種機率分配狀況，比較文獻演算法Hi與靜態排程問題WSPTA和FCFS派工法則，結果顯示ACO+EDD表現在工單數大的情況優於Hi演算法，在機台數增高的情況下效果更為明顯，其中以分配三之例題效果尤其顯著。

關鍵字

蟻群最佳化 ； 交期指派策略 ； 線上排程

並列摘要

In the modern manufacturing environment, customer-order-driven has become the most popular production type. For those important orders, delay of the final product will lead to the degrading of the customer royalty and the business credibility. Also the early finished product will cost the company to find a warehouse to store the end-product before they are delivered to customers. Therefore it is important to assign appropriate due date to orders and to determine an efficient production scheduling simultaneously. Thus, this research presents a novel ant colony optimization (ACO) model for single machine scheduling and permutation flow shop scheduling problems. The ACO algorithm determines how to insert arriving jobs into the waiting line and to be operated by the idle machine(s). Meanwhile two due date quotation strategies for both single machine and permutation flowshop environment respectively are embedded with the proposed algorithm to set the due date for each job once it arrives. Three sets of large-size instances consisting of 100, 500, and 2500 jobs, and one (single machine), three and five (flowshop) machines respectively are tested with three distributions for processing time and inter-arrival time of each job. The performance of the ACO algorithm is compared with a heuristic algorithm Hi. The computational results show that ACO+EDD performs competitively particularly when the problem size increases.

並列關鍵字

Ant colony optimization ； due date quotation ； on-line scheduling

參考文獻

4. 湯璟聖，2003，「動態彈性平行機群排程的探討」，中原大學，碩士論文。

3. 陳煜昇，2007，「蟻群最佳化演算法於單機線上排程問題之研究」，元智大學，碩士論文。

1. 洪琦茹，2005，「蟻群演算法於單機多目標排程問題之應用」，元智大學，碩士論文。

2. 陳柔君，2005，「蟻群演算法於等效平行機台排程問題之研究」，元智大學，碩士論文。

6. Alidaee, B., Panwalkar, S. S., “Single stage minimum absolute lateness problem with a common due date on nonidentical machines,” Journal of the Operational Research Society, Vol. 44, pp. 29–36, 1993.