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

Abstract

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

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

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.