以基因演算法搭配簡潔染色體表達法求解分散且彈性零工式排程

Abstract

本研究提出四個基因演算法 (GA_JSA, GA_JS, GA_J, and GA_JCS) 來求解分散且彈性零工式排程 (distributed and flexible job shop scheduling, DFJS) 問題。DFJS問題包含三個排程決策，(1) 工件指派：工件指派到哪一個製造單元，(2) 作業排序：機臺上的各作業要如何排序，(3) 作業指派：作業指派到哪一臺機臺上加工。因此，求解DFJS問題是一個三維度解空間 (3-dimensional solution space) 搜尋問題，其中每一個維度代表一種決策。GA_JS發展一種全新且簡潔的染色體表達法 (chromosome representation) SJOB，它是一個工件序 (job sequence)，以一維型式來表示三維排程解；也就是說，染色體空間 (chromosome space) 是一維 (1-dimensional, 1D)，解空間是三維 (3-dimensional, 3D)，並發展解碼規則 (decoding rules) 將染色體轉變成排程解。給定一個排程解，透過關鍵製造單元排程微調 (critical-cell refinement) 來產生更好品質的排程解；並發展編碼規則 (encoding rules) 將此排程解轉變成染色體。解碼規則是設計來獲得較好的排程解，所謂好的排程解是具有負荷平衡 (load-balanced)；關鍵製造單元排程微調與編碼規則是提供一種新的方法 (不是透過基因運算) 來產生新的染色體，此染色體稱為影子染色體 (shadow chromosomes)。四個基因演算法差別在於：GA_J使用SJOB染色體表達法；GA_JS是GA_J的延伸，並且發展影子染色體；GA_JSA是GA_JS的延伸，並且發展全製造單元排程微調 (all-cell refinement) 來產生更好品質的影子染色體；GA_JCS所使用的染色體表達法稱為SJOB-CELL，它是SJOB表達法的延伸，將工件指派決策直接表達在染色體裡，並使用解碼規則將染色體轉變成排程解。實驗結果以求解品質做為比較，GA_JSA > GA_JS > GA_JCS > GA_J = IGA (De Giovanni and Pezzella, 2010)，此IGA演算法是到目前為止求解DFJS問題績效最好的基因演算法。除此之外，實驗結果也顯示影子染色體對於求解DFJS問題有正面效果。

This paper proposes four genetic algorithms (GA_JSA, GA_JS, GA_J, and GA_JCS) for solving distributed and flexible job-shop scheduling (DFJS) problems. A DFJS problem involves three scheduling decisions: (1) job-to-cell assignment, (2) operation-sequencing, and (3) operation-to-machine assignment. Therefore, solving a DFJS problem is essentially a 3-dimensional solution space search problem; each dimension represents a type of decision. The GA_JS algorithm is developed by proposing a new and concise chromosome representation SJOB, which models a 3-dimensional scheduling solution by a 1-dimensional scheme (i.e., a sequence of all jobs to be scheduled). In GA_JS, we develop a decoding method to convert a chromosome into a solution. In addition, given a solution, we use a refinement method to improve the scheduling performance and subsequently use a encoding method to convert the refined a solution into a chromosome. The decoding method is designed to obtain a “good” solution which tends to be load-balanced. In contrast, the refinement and encoding methods of a solution provides a novel way (rather than by genetic operators) to generate new chromosomes, which are herein called shadow chromosomes. Comparing to IGA (De Giovanni and Pezzella, 2010) which is the up-to-date best-performing genetic algorithm in solving DFJS problems, GA_J is distinct in using SJOB chromosome representation; GA_JS is an extension of GA_J by additionally including the development of shadow chromosomes; GA_JSA is an extension of GA_JS by the inclusion of an all-cell refinement procedure which can yield shadow chromosomes with better quality; and GA_JCS is distinct in using SJOB-CELL chromosome representation. GA_JCS is an extension of GA_JS by additionally including the job-to-cell assignment decision. In terms of solution quality, GA_JSA > GA_JS > GA_JCS > GA_J = IGA. Experiment results indicate that the inclusions of shadow chromosomes have a positive effect in solving DFJS problems.