應用禁忌搜尋法求解跳躍式流線型生產線不得待機工件之排程

Abstract

本論文探討JNWF的排程問題。JNWF排程問題是限制工件在生產過程中不能有等待機台的情況發生，且各工件經過機台的先後順序相同，但依工件的不同，加工過程中可能會跳過某些機台加工。本研究根據JNWF排程問題的特性，以總排程時間最小化為目標。利用禁忌搜尋法 (tabu search) 提出演算法 (PETS)，求解各工件佔用機台的優序。本研究與Radran’s heuristic (1994) 求解JNWF排程問題方法，分別就起始解、最終解，及運算時間進行比較。結果顯示，在起始解及最終解的總排程時間明顯優於Radran’s heuristic (1994) 所提出的方法，唯在運算時間及機台數較少的情境，無顯著差異。

Our study investigates the scheduling problem for the environment of Jumping No-Wait flowshop (JNWF), where jobs are not allowed to wait for machines during the production processes. In the production processes, all jobs are ordered visit a sequence of m machines and some jobs skip some machines in the sequence, which is called "machine jumping". The problem is to determine the sequence of jobs being released for the first machine and our objective is to minimize the makespan. In this paper, we study the characteristics of JNWF scheduling problem and propose a Probability Enhanced Tabu Search (PETS) based on improved Tabu search method. We then compare our heuristic with Radran’s heuristic (1994), on the makespan and the computational time. The numerical studies show that our heuristic performs more effectively and efficiently than Radran’s heuristic on solving the JNWF problems.