以基因演算法求解交期導向之分散彈性零工式排程

Abstract

本論文是求解分散彈性零工式排程問題(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.