粒子群聚演算法於FMS之機台與車輛同步排程

Particle swarm optimization approach for simultaneous scheduling of machines and AGVs in FMS

許雅寧

指導教授 ： 林則孟

國立清華大學/工學院/工業工程與工程管理學系/碩士(2014年)

摘要

彈性製造系統系統(Flexible Manufacturing System, FMS)中除了機台資源外還包含搬運系統如自動物料搬運車輛(Automatic guided vehicles, AGV)，而車輛搬運時會導致機台閒置，因此在本研究目標是要同步(Simultaneous)處理作業排程與車輛排程，使總完工時間(Makespan)最小化。考量作業排程與車輛排程是一複雜的NP-Hard問題，本研究將利用粒子群演算法(Particle Swarm Optomization)結合粒子位置交換機制(Muti-type individual enhancement scheme)產生作業排程，並且與車輛排程演算法結合替每項加工作業選擇搬運車。
文獻中求解同時排程問題多以數學規劃法，車輛搬運工件的時間是以搬運距離除以車速，未考慮到車輛在途中可能因為壅塞而延遲搬運時間或是發生車輛鎖死(deadlock)，因此本研究加入車輛區域控制(zone-control)。由於FMS中，機台為多功能機台，工件的同一作業可選擇替代路徑與機台，此特性增加排程的複雜性。同時比較基礎模型與兩個延伸模型，觀察simple model 與 complex model之差異。另外，在現實的FMS中不同工件的作業時間有變異性，因此考量工件加工時間具有隨機性，由於模型具有隨機因子，若只模擬一次實驗隨機性質所造成的誤差值可能會影響判斷，若模擬太多次則會浪費時間成本。因此本研究OCBA(Optimal Computing Budget Allocation)適當的分配模擬資源給予無法分辨出優劣的方案或變異太大的方案，以最少的模擬資源找出最佳方案，結果顯示可以降低65%的模擬資源。

關鍵字

Flexible manufacturing system ； Scheduling ； Automated guided vehicle ； Zone-control ； Particle swarm optimization ； Optimal computing budget allocation

參考文獻

[1]王治平，”實際零工式生產排程問題的派工法則”，政治大學資訊管理研究所 碩士論文，2003。

[4]張祐翔，”應用模擬最佳化於FMS之機台與車輛同步排程”，清華大學工業工程與工程管理所碩士論文，2013。

[6]Abdelmaguid, T. F.,Nasef, A. O., Kamal, B. A. and Hassan, M. F., “A hybrid GA/Heuristic approach to the simultaneous scheduling of machines and automated guided vehicles”, International Journal of Production Research, Vol.42, No.2, 2004, pp267-281.

[7]Anwar, M. F. and Nagi, R., “Intergrated scheduling of material handling and manufacturing activities for JIT production of complex assemblies”, International Journal of Production Research, Vol.36, No.3, 1993, pp653-681.

[9]Bilge, U. and Ulusoy, G., “A time windows approach to simultaneous scheduling of machines and material handling system in an FMS”, Journal of Operations Research, Vol.43, No.6, 1995, pp1058-1070.