蟻群演算法於單機多目標排程問題之應用

Ant Colony Optimization for Multi-Objective Single Machine Scheduling Problem

洪琦茹(Chi-Ru Hung)

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

摘要

生產排程是複雜且困難的，越是重要的訂單，越不允許延遲交貨的狀況發生，否則伴隨而來的各項違約成本與商譽損失，都將造成公司營運上有形或無形的損失，而太早提前完工則會導致完成品的庫存成本越高。若能以一個有效率的生產排程來解決生產線上的問題與顧客的需求，減少提前完工時間、延遲完工時間造成對生產上的傷害，對工廠來講是非常重要的。

本研究提出多種不同蟻群數、不同費洛蒙更新方式及不同局部搜尋機制的蟻群演算法，來求解單一機台上總加權延遲時間最小化和總加權提前完工時間最小化問題。蟻群演算法內狀態轉換法則之貪婪法則 ( 值)會因所需求解問題的不同而有所差異，在本研究中使用派工法則COVERTAU來求解總加權延遲時間，派工法則WMR則用來求解總加權提前完工時間。並針對總螞蟻數、局部搜尋的影響與參數設定做一探討。每種不同的蟻群演算法以柏拉圖最佳前緣來做比較，其中以五蟻群五區局部搜尋 – 混合全域更新法的蟻群演算法表現最佳。本研究亦期望提供多組排程方案，以供管理者在決策時的參考。

關鍵字

蟻群演算法、單機排程、多目標

並列摘要

Production scheduling problem is complex and difficult in real world. Delay of the orders may cause the loss of business credibility, but on the hand the too early finish-up may lead to the tremendous inventory cost. Therefore, how to plan and implement an efficient production scheduling to meet customers’ due and demands has become a very important issue to enterprises.

This research proposes several ant colony optimization algorithms with different number of colonies, pheromone updating rules, and local search mechanisms. Two objectives were considered simultaneously – minimize total weighted tardiness and minimize total weighted earliness. In order to find an efficient local heuristic for each objective, a comprehensive study of dispatching rules is employed. The COVERTAU dispatching rule is selected for the total weighted tardiness objective while the WMR rule is used to assist the optimization of total weighted earliness. Experiments were conducted to investigate the effects of the number of ants, local search, and parameter settings. Using the best parameter settings, Pareto optimal front of each algorithm is collected to compare their performance. The ant colony algorithm with five colonies, five-region local search, and a mixed pheromone updating rule outperform others. This research also hopes to provide decision-maker many practical alternatives while facing different scheduling scenarios.