以基因演算法求解雙流線型工廠排程

A Genetic Algorithm for Scheduling Dual Flow Shops

劉謹銘(Chin-Min Liu)

指導教授 ： 巫木誠

國立交通大學/管理學院/管理學院碩士在職專班工業工程與管理組/碩士(2009年)

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

摘要

本研究驗證一個雙流線型工廠的排程問題，在允許跨廠的加工情況下，排程目標以最小化寬裕時間的變異係數，而寬裕時間是指工件到期日與總加工時間的差異；此排程問題牽涉到二種決策，一個是工件途程選擇，另一個是工件加工順序安排。以基因演算法搭配最早到期日為派工法則下，發展出作此二種決策的方法。基因演算法數據化實驗顯示合適的跨廠生產政策在績效上會優於單廠排程的生產政策，特別是兩廠在生產效率不一致的情境下更是顯著。

本研究發展了群組化巨集演算，此想法是同時考慮到節省設置時間與到期日為基礎的需求。我們透過基因演算法的方式解決了此問題，並證明群組化巨集演算有好的績效。當得到近似最佳解時，我們即可做出每一個工件在跨廠途程選擇與機台加工順序安排的決策。

關鍵字

排程 ； 跨廠 ； 流線型工廠 ； 設置時間 ； 到期日 ； 基因演算法

並列摘要

This research examines a dual flow shop scheduling problem, in which cross-shop processing is allowed. The scheduling objective is to minimize coefficient of variation of slack time (ST), where ST of a job denotes the difference between its due date and total processing time. The scheduling problem involves two decisions: job route assignment (assigning jobs to shops) and job sequencing. A genetic algorithm (GA), embedded with EDD (earliest due date) dispatching rule, is developed for making the two decisions. Numerical experiments of the GA algorithm indicate that the performance of adopting cross-shop production policy may significantly outperform that of adopting single-shop production policy, in particular while the two flow shops are asymmetrically designed.
This research develops a Grouping heuristic algorithm, which conception is considered to save setup time and due-date-based demand simultaneously. We solve it by GA (Genetic Algorithm) and prove Grouping heuristic algorithm have a good performance. While obtaining approximate optimal solution, we can decide the route assignment of jobs and the job sequencing of machines.

並列關鍵字

scheduling ； cross-plant ； flow shop ； setup time ； due date ； genetic algorithm (GA)

參考文獻

〔23〕 林友婷，「動態瓶頸有限產能規劃：以覆晶載板生產為例」，中原大學工業工程與管理研究所，碩士論文，2006年。

〔1〕 Allahverdi, A. and J.,Mittenthal,“Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time”, Naval Research Logistics , 41, pp 677- 682 ,1994

〔2〕 Archimede, B., et al., “Robustness evaluation of multisite distributed schedule with perturbed virtual jobshops” , Production Plan-ning & Control, 14, 55-67, 2003.

〔3〕 Bhatnagar, R., et al., “Models for Multi-Plant Coordina-tion” , European Journal of Operational Research, 67, 141-160, 1993.

〔4〕 Caroloin, T., et al., “Multi-site planning: non flexible production units and set-up time treatment”, Proceedings of the Emerging Technologies and Factory Automation, Vol.3, 1995.