標題: 以基因演算法求解交期導向之分散彈性零工式排程A Genetic Algorithm for Meeting Due-Date in Distributed and Flexible Job-shop Scheduling 作者: 蔡侑陵巫木誠Tsai, Yu-LingWu, Muh-Cherng工業工程與管理系所 關鍵字: 分散彈性零工式生產排程;基因演算法;交期;染色體表達法;Distributed and Flexible Job-shop;Genetic Algorithms;Due Date;Chromosome Representation 公開日期: 2016 摘要: 本論文是求解分散彈性零工式排程問題(distributed and flexible job shop scheduling, DFJS)，此研究問題複雜度為NP-hard問題。而DFJS包含了三個排程決策，第一決策為工件指派(job-to-cell assignment)：工件指派到製造單元；第二決策為作業指派(operation-to-machine assignment)：作業指派到機台；第三決策為作業排序(operation-sequencing)：機台前的作業加工順序。本研究主要的構想為求解DFJS排程問題考量了工件的交期(due date)，目標是最小化總延遲時間(total tardiness)。針對過去三篇文獻在求解DFJS排程問題所發展的基因演算法修改之，並提出三個基因演算法(GA_OP_D, GA_JS_D, and IGA_D)。而這三個基因演算法的流程是相似的，差別在於使用了不同的染色體表達法(SOP, SJOB, and SG)。最後透過實驗結果顯示，GA_OP_D演算法在多數的實驗例題中，解品質與計算時間是優於其他兩個演算法。This research studies a distributed and flexible job shop (DFJS) scheduling problem which involves three scheduling decisions: (1) job-to-cell assignment, (2) operation-to-machine assignment, and (3) operation-sequencing. The complexity of solving DFJS problems is NP-hard. This research solves the DFJS scheduling problem for meeting due date, and the scheduling objective is to minimize total tardiness. This study proposes three genetic algorithms (called GA_OP_D, GA_JS_D, and IGA_D) which are adapted from prior studies to solve the DFJS problems. The three algorithms are similar in algorithmic flow but distinct in using different chromosome representations (called SOP, SJOB, and SG). Experiment results indicate that algorithm GA_OP_D outperforms the other two algorithms in terms of solution quality and computation time. URI: http://etd.lib.nctu.edu.tw/cdrfb3/record/nctu/#GT070353306http://hdl.handle.net/11536/143421 Appears in Collections: Thesis