非相關平行機台之彈性生產排程模式

A Flexible Scheduling Model for the Unrelated Parallel Machines Production System

黃秋媚(CHIU-MEI HUANG)

指導教授 ： 江瑞清

中原大學/工學院/工業工程研究所/碩士(2007年)

https://doi.org/10.6840/cycu200700234

摘要

本研究主旨在探討機台合適度與加工順序相依整備時間限制下的非相關平行機台排程問題。本研究基於訂單的重要程度不同、訂單之間具有加工順序相依整備時間，加上機台與訂單的合適度限制，使得機台高階低用，訂單未能得到適當的配置，造成訂單的延遲及產能的浪費情形頻繁，因此本研究目的在於滿足訂單交期及減少因不當配置所造成系統中不必要產能浪費等成本支出，以加權延遲懲罰成本及產能浪費成本最小化為目標，尋求最佳化的排程方式，促使生產系統具備機器、產品、製程、作業的彈性度，同時可減少生產排程的程序、確保機台調度的彈性及提高機台有效生產的時間。
本問題符合學術上困難度極高的組合最佳化問題（Combinatorial Optimization Problem），複雜度已證明為NP-Complete，然而該問題目前依舊是一項尚未充分研究的領域。本研究運用數理規劃的規劃方法，將生產排程的觀念與條件進行轉換，發展出一套符合產業特性與需求的彈性生產排程作業規劃模式。最後結合運算組合最佳化的發展工具：ILOG OPL與範例的驗證下，確立模型的真確性與可行性。

關鍵字

非相關平行機台 ； 機台合適度 ； 加工順序相依整備時間 ； 最小化總成本

並列摘要

This research considers the scheduling problem about unrelated parallel machines with machine eligibility and sequence-dependent setup times. In practice, due to there are different importance ratings, sequence-dependent setup times and machine eligibility among orders, orders are not well allocated. Consequently, orders are delayed and capacity is not well utilized. Through this, the purpose of scheduling is to meet delivery dates and to reduce the capacity wastes. In this research, we expect to propose a scheduling operation model that can generate an optimal schedule to achieve the objectives of minimizing total weighted lateness and waste cost, and then make the production system can be more flexible in the arrangement and scheduling of machine, product, process, operation etc.
This problem is a combinatorial optimization problem, which is proved as a NP- complete problem. However, the previous researches are falling short in the problems about unrelated parallel machines with machine eligibility and sequence-dependent setup times. In view of this, this study, based on the concepts and constraints of production scheduling, uses mathematical programming method to develop a flexible scheduling model mainly applied in a one-stage parallel-processor scheduling problem. Also, we have implemented it with an optimization software, ILOG OPL, to confirm the applicability of this model.

並列關鍵字

Minimize Total CostTimes ； Sequence-dependent Setup Times ； Sequence-dependent Setup Unrelated Parallel Machines、M ； Minimize Total Cost ； Unrelated Parallel Machines、Machine Eligibility

參考文獻

湯璟聖，「動態彈性平行機群排程的探討」，中原大學工業工程研究所碩士論文，民國92年。

王彥文，「印刷電路板鑽孔作業生產排程之研究」，元智大學工業工程與管理研究所碩士論文，民國91年。

李勝隆，「基因演算法於印刷電路板鑽孔排程之應用」，元智大學工業工程與管理研究所碩士論文，民國92年。

徐烈昭，「應用塔布搜尋法於非等效平行機台之研究－以PCB鑽孔作業為例」，元智大學工業工程研究所碩士論文，民國90年。

Adamopoulos, G. I. and Pappis, C. P., “Scheduling under a common due-date on parallel unrelated machines,” European Journal of Operational Research, Vol. 105, No. 3, 1998, pp. 494-501.