應用粒子群演算法求解雙機流程工廠群組排程問題

A PSO Based Algorithm for Two-Machine Flow Shop Group Scheduling Problem

劉俊宏(Chun-Hung Liu)

指導教授 ： 劉正達

國立虎尾科技大學/管理學院/經營管理研究所/碩士(2010年)

摘要

本研究主要探討雙機流程工廠(Two-machine Flow shop)群組排程(Group Scheduling)總完工時間最小化之問題，且考慮了工作順序相依整備時間(Sequence-Dependent Setup Times)、工作順序相依拆卸時間(Sequence-Dependent Removal Times)及工作轉換時間(Transportation Times)等。群組排程問題是屬於NP-hard問題，而本研究的群組排程問題較之傳統群組排程問題更具一般性。
本研究提出一種新的粒子群演算法(Particle Swarm Optimization, PSO)編碼方式來求解雙機群組流程工廠排程問題，可同時求解群組與群組之間的排序以及群組內工作的排序，我們測試了162個隨機產生的測試問題，測試問題群組數最大為15，群組內的工作數最多為10，為了衡量所提PSO解題品質，本研究亦提出三種下界(Lower Bound)做為比對基準。從有限的數值模擬結果顯示，PSO於求解各種規模問題，解題品質相當良好，且本研究所提出三種下界亦能有效的作為衡量基準。

關鍵字

群組排程問題 ； 粒子群演算法 ； 工作順序相依 ； 總完工時間最小化

並列摘要

This paper investigates the two-machine flow shop group scheduling problem with job transportation times between machines, sequence-dependent setup and removal times. The objective is to minimize the total completion time. As known, this problem is a NP-hard problem that generalizes the typical two-machine group scheduling problems. In this paper, a PSO based algorithm with an effective coding scheme is proposed to effectively solve various 162 instances with group numbers up to 15. Note that the proposed coding scheme simultaneously determines the sequence of jobs in each group and the sequence of groups. In addition, three different lower bounds are developed to evaluate the effectiveness of the PSO algorithm. Limited numerical results show that the proposed PSO algorithm performs well for all test problems.

並列關鍵字

Group scheduling ； Sequence-dependent ； PSO

參考文獻

9.冼祐臣(2008)，粒子群演算法於火力機組排程問題之研究，中原大學，碩士論文。

12.鄒佳臻(2007)，粒子群演算法結合低閒置策略於生產排程之應用，中原大學，碩士論文。

11.鄭舜源(2006)，應用限制式粒子群基因演算法於解決排程問題之研究，清雲科技大學，碩士論文。

4.賴阮明(2008)，整合粒子群最佳化與蜂群演算法求解彈性零工式生產排程問題之研究，台北科技學，碩士論文。

14.沈銘倫(2008)，應用模擬退火法與離散粒子群演算法在排列流程式排程問題研究，台北科技大學，碩士論文。