考慮批量分割於混合流程型生產排程問題

Hybrid Flow Shop Scheduling with Lot Split Problem

張嘉軒(Chia-Hsuan Chang)

指導教授 ： 林則孟

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

摘要

本研究針對混合流程型生產系統之生產排程，探討訂單拆批與機台指派同步規劃。拆批為將訂單拆分成數個子批，機台指派則為將訂單指派到各站可加工的機台群。本研究探究三生產站之混合流程型生產系統，每站有多個非等效平行機台群，每機台群又包含一至數台的等效平行機台。考量到訂單加工時間具有隨機性，各產品依照期產品規格，對於各站機台群又有選擇的限制。為了降低訂單平均完成時間，批量分割將會在此生產系統使用，將各訂單拆成數個子批，藉由加工作業重疊，以加快訂單在這三站的流程時間。
綜觀上述各點，本研究將探討二大問題，一為批量分割，二為機群指派。批量分割是將各訂單分割成數個相同大小的子批，並找尋合適的分割數量；機群指派則是將訂單指派至各站適合之加工機群。在同步考量拆批與機台指派的情況下，使得求解空間過大、問題過於複雜，因此本研究使用基因演算法進行可行解域中的方案搜尋。從結果可以發現，拆批確實可以降低訂單平均完成時間，而且變動拆批績效表現較等量拆批佳。除此之外，考量到訂單加工時間具有隨機性之情況，需藉由多次的抽樣來減少變異，因而增加模擬次數。因此，本研究利用資源分配最佳化(Optimal Computing Budget Allocation, OCBA)來提升模擬效率，結果顯示可以降低76%的模擬資源。

關鍵字

批量分割 ； 機台指派 ； 基因演算法 ； 資源分配最佳化 ； 混合流程型生產排程問題

並列摘要

In this research we study a hybrid flow shop scheduling with lot split and machine assignment problem, the order would be split up several sublots, and the machine assignment is that each order would be assigned to eligibility machine groups at each stage. In this research we study a three-stage hybrid flow shop production system, with several unrelated parallel machine groups at each stage, and there are some identical parallel machines at each machine group. We consider that processing time is stochastic, and each product type has its eligible machine groups. To reduce mean completion time, lot split would be used in this production system. Each order would be separated into several sublots to reduce flow time by the overlapping of operations.
All in all, this research would discuss two issues, lot split and machine group assignment. Lot split is that each order would be separated into several equal size sublots, and we look for suitable quantity. Machine group assignment is that each order would be assigned to eligible machine groups at each stage. We simultaneously consider lot split and machine group assignment, so that solution space is too large. We use genetic algorithm to search for suitable solution. From the result, we find that lot split is useful to mean completion time, and variable lot split performs better than consistent lot split. In addition, we take stochastic processing time into condition, and it spends many times to reduce the sampling variability. Therefore, we use optimal computing budget allocation to improve efficiency. Computation results indicate that it reduces 76% simulation times by using OCBA.

並列關鍵字

Lot split ； Machine assignment ； Genetic algorithm ； Optimal Computing Budget Allocation ； Hybrid flow shop scheduling problem

參考文獻

鍾雅琳，“考量派工法則與批量流於半導體封裝廠之生產排程問題”，國立清華大學工業工程與工程管理所碩士論文，2015。

Allahverdi, A. and Al-Anzi F. S., “Scheduling multi-stage parallel-processor services to minimize average response time”, Journal of the Operational Research Society, 57, 101–110, 2006.

Allaoui, H. and Artiba A., “Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints”, Computers & Industrial Engineering, 47(4), 431–450, 2004.

Chen, C. H. and Lee, L. H., “Stochastic Simulation Optimization: An Optimal Computing Budget Allocation”, 2010.

Garey, M. R. and Johnson, D. S., “Computers and intractability: a guide to the theory of NP-completeness”, San Francisco: Freeman, 1979.