以三階基因演算法搭配作業序表達法求解彈性零工式排程問題

A Three-Phase GA Algorithm With An Operation-Sequence-Based Chromosome Representation For Scheduling Flexible Job Shops

黃建翰(Chien-Han Huang)

指導教授 ： 巫木誠

國立交通大學/管理學院/工業工程與管理系所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00220

摘要

本論文主要在探討彈性零工式排程問題(flexible job-shop scheduling problem, FJSP)，FJSP排程問題包括兩項子決策，分別為(1)作業的機台指派(operation-to-machine assignment)，(2)機台前的作業加工順序(operation sequencing for each machine)。FJSP問題的複雜度已被證明是NP-hard，過去研究發展各種不同巨集啟發式演算法(meta-heuristic algorithms)來求解。本論文採用基因演算法(genetic algorithm；GA)的架構搭配作業序表達法，為一個新的染色體表達法(簡稱Sop)，發展出一新演算法(稱為GA_Sop)來求解FJSP問題。所謂染色體表達法是指解的表達法，Sop表達法的構想是將作業排序；亦即一個染色體就是一個特定的作業排序(a particular sequence of operations)。在給定某一染色體(作業排序)的條件下，本研究發展數種啟發式演算法(heuristic methods)，可藉此導出此染色體相對應的作業指派子決策。本研究是以最大完工時間(makespan)為目標函數。

關鍵字

彈性零工式排程問題 ； 基因演算法 ； 巨集啟發式演算法 ； 解表達法

並列摘要

This research is concerned with the scheduling of a flexible job-shop problem (called FJSP), which involves two sub-decisions: (1) operation-to-machine assignment (2) operation sequencing for each machine. Most prior studies proposed meta-heuristic algorithms for the FJSP problem. This research proposes a new solution representation (called Sop), which is intended to model a particular sequence for all operations. Given a particular Sop, by some heuristic rules, we can obtain its two corresponding sub-decisions; which in turn represents a particular scheduling solution. Based on the Sop representation, this research adopts the existing architecture of genetic algorithm (GA) and develops a meta-heuristic algorithm (called GA_ Sop) to solve the FJSP problem.

並列關鍵字

flexible job-shop scheduling ； genetic algorithm ； meta-heuristic algorithms ； solution representation

參考文獻

戴邦豪，「應用混合式染色體表達法於具順序相依家族整備時間之流線型製造單元排程」，國立交通大學工業工程與管理學系碩士論文，2010。

Brandimarte, P., 1993. Routing and scheduling in a flexible job shop by taboo search. Annals of Operations Research, 41, 157-183.

Carlier, J., and Pinson, E., 1989. An algorithm for solving the job-shop problem. Management Science, 35, 164-176.

Goncalves, J.F., Mendes, J.J.M., and Resende, M.G.C., 2005. A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research, 167, 77-95.

Gao, J., Gen, M., Sun, L., and Zhao, X., 2007. A hybrid of genetic algorithm and bottleneck shifting for multi-objective flexible job shop scheduling problems. Computers & Industrial Engineering, 53, 149-162.