蟻群最佳化演算法於單機線上排程問題之研究

Ant Colony Optimization for Single Machine On-line Scheduling Problem

陳煜昇(Yu-Sheng Chen)

指導教授 ： 梁韵嘉

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

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

摘要

排程問題是複雜且困難的，越是重要的訂單，越不允許延遲的狀況發生，否則極有可能導致各項成本的增加與顧客忠誠度的下降，進而對公司造成有形或無形的損失，在另ㄧ方面，太早完工則容易提升庫存成本，因此以一個有效率的交期指派策略訂定適當的交期時間，並妥善安排各工件之加工順序，在公司與客戶之間找到對雙方皆有利的均衡點是十分重要的。過往排程的研究中多針對靜態問題進行研究，但在真實的生產環境中，各工件的生產資訊往往是無法事先預知的，因此為了符合真實的生產狀況，本研究利用蟻群最佳化（Ant Colony Optimization；ACO）演算法首次針對單機線上排程問題進行求解，期望能在符合訂定的交期時間下獲得近似最佳解的排程結果。
本研究提出兩種蟻群最佳化演算法的架構－ACO-I與ACO-II，透過兩階段式的方法，首先在工件抵達時透過ACO選擇工件插入位置，同時考慮結合不同派工法則的局部搜尋機制改善排序，接著利用已知的資訊決定工件的交期時間，之後分別以總加權交期時間與總加權報價前置時間為目標，在考慮三種不同機率分配與工件數組合所產生的間隔到達時間和處理時間的測試例題下，與文獻中的演算法( )以及靜態單機排程中的WSPTA和FCFS派工法則進行比較，結果顯示ACO-II的整體表現優於ACO-I與 演算法，而派工法則中以EDD的助益最大，亦即ACO-II+EDD在不同的測試例題下，整體的求解表現最好。

關鍵字

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

並列摘要

In reality, delay of the orders may cause the loss of business credibility. On the contrary, earliness of the orders may lead to enormous inventory cost. Hence, it is important to assign an appropriate due date to the orders and determine an efficient production scheduling. Thus, the purpose of this research is to develop an ant colony optimization (ACO) algorithm hybridized with different local search mechanisms to solve the single machine on-line scheduling problem. The objective of the problem is to minimize the total weighted due date and total weighted quoted lead time. When a job arrives, the production sequence will be determined and a due date will be assigned to the job accordingly by using a two-phase approach. The first phase applies the ACO algorithm to insert the arriving job into the waiting list, while the second phase assigns a slack time, which is calculated according to limited information about the future, to determine the due date of the job. Three large size instances consisting of 100, 500, and 2500 jobs and associated with three distributions for the processing times and inter-arrival times of jobs respectively are tested. Two ACO algorithms are proposed and compared with a heuristic algorithm Hi from the literature and two offline dispatching rules WSPTA and FCFS. The computational results show that ACO-II+EDD is able to solve the on-line scheduling problem effectively.

並列關鍵字

Ant Colony Optimization ； Due Date Assignment ； On-line Scheduling

參考文獻

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

蕭裕民，2006，「蟻群最佳化演算法於多目標平行機台排程問題之研究」，元智大學，碩士論文。

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

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

Tian, Y., J. Song, D. Yao, and J. Hu, “Dynamic Vehicle Routing Problem Using Hybrid Ant System,” Intelligent Transportation Systems, Vol. 2, pp. 970-974, 2003.