共用機台之跳躍式不允許等待流程式生產排程

Abstract

排程問題在產業界中扮演著重要的課題，本研究提出JNWF-SCM排程問題的演算法。所謂JNWF-SCM生產線，表示在流程式生產線中，工件一旦進入生產線加工，就不能有待機的情況發生，且所有工件的前段加工是在同一機台作業，後段作業則會依據產品不同而傳送至某些機台來加工。因此加工過程中，工件除了有不可待機的條件之外，工件途程有特殊的共用機台(starting common machine)特性以及跳機台(jumping)特性。本研究根據JNWF-SCM排程問題的特性，以禁忌搜尋法(tabu search)為架構，發展一套演算法(ITS)來求解，以最小化總排程時間為目標，決定工件的投料時間。本研究設計了一系列的案例來執行，並以解的總排程時間及其穩定度、與求解時間作為演算法的評判績效，實驗結果發現本研究所提出的方法有較佳的表現，大型問題上有更明顯的優勢。

This study proposed an algorithm to solve the jumping no-wait flowshop with a starting common machine (JNWF-SCM) scheduling problem. JNWF-SCM indicates that if a job is released to a flowshop production line, then its operations must be carried out with no delay in the production line. All jobs must be processed in the starting machine and at least one machine in the rest of the others. JNWF-SCM has two special properties, starting common machine and the jumping several machines from starting common machine to the end of the production line. A tabu search approach is proposed for the JNWF-SCM scheduling problem with the makespan minimization criterion. The results of the simulated experiment show that our approach performs better than other algorithms, especially in the large scale problems in term of both solution quality and computational time.