最小化總流程時間之單階群組排程研究

群組化生産系統之排程作業簡稱爲群組排程。將個別工件依特定的屬性或製程，透過分類及編碼而形成工件族，因此，生産系統可配合工件族指派到專屬的機器群來設計。本文考慮單地階加工中心，可處理若干工件族之加工作業的排程問題，機器若連續處理同一族之工件時，不需再有整備時間，若換族加工時則需要整備時間，這和一般排程將整備時間併入虛理時間而不受加工順序影響的假設不同。實際上，若能有效地實施群組排程將可減少整備次數而縮短製程時間。本文以總流程時間爲績效衡量凖則進行研究，因爲問題本質爲NP-hard，故求解工作分兩部分進行，首先發展出一套探索式演算法，能迅速地求得最佳解或近似最佳解，經由資料測試結果顯示，最佳解題率均高達90%以上，而平均求解時間則不到分枝界限法的百分之一。再者，以探索式所得結果作爲起始解，配合淩越倏件及下界值的建構，提出整合式分枝界限法，能夠在合理的時間內，求得最佳解。

關鍵字

群組排程；工件族；整備時間；製程時間；總流程時間

並列摘要

The integration of production scheduling with group technology has come to be called group scheduling. In this system, the classification and coding procedure for each so called part family is arranged according to the similarity of the attributes or manufacturing processes of the individual components. Under this system, therefore, a production system relating each part family to a specific machine group can be designed. The present study limits itself to the scheduling problems associated with single stage GT processing centers. In this context, we find that although a new setup is required when moving between jobs of different families, no new setup is required when moving between jobs of the same family. This is different from the traditional research of scheduling which assumes the setup lime for a job is independent of job sequencing and, therefore, could be included in the processing time for each job. Our study found that by effectively implementing group scheduling the number of setups was reduced and consequently the make span was diminished. Our study addressed moat specifically performance measures of total flow lime. Since this problem is NP-hard, we developed a heuristic approach to derive a nub-optimal solution. The computational results indicate the heuristic approach we developed had a very high rate to get the optimal solution, above 90%, and its running time is really short. The solution was then used as the initial point of branch and bound procedure. Further, several dominate rules and a lower bound of the optimal flow time were developed. The integrated branch and bound procedure we developed can get the optimal solution within reasonable time.

並列關鍵字

group scheduling ； part family ； setup time ； make span ； flow time

參考文獻

Ahn, B. H.,Hyun, J. H.(1990).Single Facility Multi-class Job Scheduling.Computers and Operations Research.17,265-272.

Google Scholar

Bruno, J.,Sethi, R.(1978).Task Sequencing in a Batch Environment with Setup Times.Foundations of Control Engineering.3,105-117.

Google Scholar

Bukchin, J.,Tzur, M.,Jaffe, M.(2002).Lot Splitting to Minimize Average Flow-time in a Two-machine Flow-shop.IIE Transactions.34,953-966.

Google Scholar

Buzacott, J. A.,Duton, S. K.(1971).Sequencing Many Jobs on a Multi-purpose Facility.Naval Research Logistics.18,75-82.

Google Scholar

Crauwels, H. A. J.,Potts, C. N.,Van Wassenhove, L. N.(1997).Local Search Heuristic for Single Machine Scheduling with Batch Set-up Times to Minimize Total Weighted Completion Time.Annals of Operations Research.70,261-279.

Google Scholar

國際替代計量

最小化總流程時間之單階群組排程研究

全文下載

主題瀏覽