多階平行機台工件不允許等待之流程式生產排程

Abstract

本研究探討在多階段中有多部平行等效機台的生產系統，工件不允許等待之流程式生產排程問題（簡稱NWF-P）。NWF-P生產線是指在流程式生產線中，工件一旦進入生產線，不允許有待機的情形發生。本研究根據此問題的特性，以最小化總排程時間為目標，提出三個禁忌搜尋演算法(TS1、TS2與TS3)，求解各工件佔用機台的優序。TS1是以傳統隨機方式挑選工件找出鄰近解，TS2是依據各工件與前一排序相鄰的工件在各機台的閒置時間，做為工件被挑選的機率，TS3是針對階段一的平行機台為考量找出鄰近解。TS3的求解時間較TS1與TS2小，且能求得較小的總排程時間。權衡總排程時間與機台利用率，本研究提出決定各階段最適機台數量的方法。

This research deals with the problem of N jobs on parallel machines in S successive stages with the constraint that a job after being processed by the first stage’s machine is not allowed the waiting time between two consecutive operations. We call this problem as no-wait flowshop with parallel machines scheduling problem (NWF-P). The objective is to find a schedule that would minimize the makespan. First, considered the machine idle times, we propose an initial solution, named Revised MDA1 and Revised MDA2, for jobs schedule and the assignment of jobs to machines in all stages. Then based on the proposed initial solution, three tabu search algorithms, named TS1, TS2 and TS3, are developed. We evaluate the performances of TS1, TS2 and TS3. with 640 scenarios for experiments. It shows that TS3 is superior to TS1 and TS2 in makespan values and computational time. Finally, considered the tradeoff between machine utilization rates and makespan values, we propose a method to determine the machine numbers in each stage.