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

No-Wait Flowshop Scheduling with Multi-Stage Parallel Machines

曾秀文(Hsiu-Wen Tseng)

指導教授 ： 許錫美

國立交通大學/管理學院/工業工程與管理系所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00327

摘要

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

關鍵字

No-Wait ； 流程式生產 ； 平行機台 ； 總排程時間 ； 禁忌搜尋法

並列摘要

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.

並列關鍵字

No-Wait ； Flowshop ； Parallel Machines ； Makespan ； Tabu search

參考文獻

[1] T. Aldowaisan, and A. Allahverdi(2003), “New heuristic for no-wait flowshops to minimize makespan,” Computers and Operations Research Vol. 30, pp.1219-1231.

[2] A. Allahverdi, and T. Aldowaisan(2002), “No-wait flowshops with bicriteria of makespan and total completion time,” Computers & Operations Research Vol. 30, pp.1219-1231.

[3] E. Bertolissi(2000), “Heuristic algorithm for scheduling in the no-wait flow-shop,” Journal of Materials Proceeding Technology Vol.107, pp.459-465.

[4] Bo Liu, Ling Wang, and Yi-Hui Jin(2007), “An effective hybrid particle swarm optimization for no-wait flow shop scheduling,” International Journal of Advanced Manufacturing Technology Vol.31, pp.1001-1011.

[5] J. Chang, W. Yan, and H. Shao(2004), “Scheduling a two-stage no-wait hybrid Flowshop with separated setup and removal times,” Proceeding of the 2004 American Control Conference Vol.216, pp.1412-1416.