NSGA-II for solving a bicriteria general job shop scheduling problem with layers

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Electronic Thesis & Dissertation > Item 987654321/89035

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/89035

Title:	NSGA-II for solving a bicriteria general job shop scheduling problem with layers
Authors:	江欣諭;Chiang, Hsin-Yu
Contributors:	工業管理研究所
Keywords:	零工式排程;工件回流;雙目標;分離弧線圖;非支配排序遺傳演算法;Job shop problem;recirculation;bi-objective;disjunctive graph;NSGA-II
Date:	2022-07-05
Issue Date:	2022-10-04 10:48:46 (UTC+8)
Publisher:	國立中央大學
Abstract:	本研究主旨在探討具有工件具回流特性的雙目標零工式排程問題，在此我們選擇最大化“stage-out”的數目以及最小化工件總延遲時間做為目標，以同時滿足短期排程規劃及長期排程規劃。“stage-out”是實務中半導體環境的每日績效之一，我們將其轉換為最小化延遲工作總件數來優化它，而最小化工件總延遲時間則可視為長期目標，為因應不同的時程規劃，我們將給予兩目標不同的截止日期。另外，我們建立了一個新的分離弧線圖，其中每個工件都具有多個層級，每個層級包含多個操作，而在層和層之間有額外的弧線去界定各層級的順序。針對我們研究的問題，我們提出了不同以往的非支配排序遺傳演算法，將原本完全隨機的變異過程改由使用局部搜索中的鄰里結構取代，盡可能有依據的改善當前的解。在實驗中我們分成兩大部分，其中一個實驗我們和過去的實例做比較，另一個實驗則是針對改善後的非支配排序遺傳演算法評估效益，最終實驗結果也證明了此改善能有效的在短時間內找到還不錯的解。 ;The main purpose of this study is to solve the bi-objective of job shop scheduling problem with recirculation. We choose to maximize the number of "stage-out" and minimize the total tardiness as objectives. Try to meet the requirements of short-term scheduling and long-term scheduling at the same time. "Stage-out" is one of the daily performances in a practical semiconductor environment, and we optimize it by converting it to minimize the total number of tardy jobs. While minimizing the total tardiness can be considered a long-term goal. For two different targets, we also give two different due dates. In addition, we proposed a new disjunctive graph, which contains multiple layers in a job and each layer contains multiple operations. There also introduce additional arcs between layers to define the processing order. In our research, we propose a non-dominated sorting genetic algorithm (NSGA-II) that is different from the traditional one. That we do the mutation operator with the neighborhood structures of local search and aim to find a good solution in a short time. In the experimental, we do two tests. First, we compare with benchmark instances to evaluate the performance of NSGA-II. Second, we compare the NSGA-II we proposed and the NSGA-II that all of the processes are depend on randomly generate. The result proves that this improvement can effectively speed up finding a good solution.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	63	View/Open

社群 sharing

Loading...