最小化總延後時間與碳排放量之平行機批次處理排程問題

Minimizing Total Tardiness and Carbon Emission for Identical Parallel Machines with Batch Processing Machines

鄭祖元(Tsu-Yuan Cheng)

指導教授 ： 應國卿

國立臺北科技大學/管理學院/工業工程與管理系碩士班/碩士(2014年)

https://doi.org/10.6841/NTUT.2014.00863

摘要

本文是針對在平行機台上的批量加工問題來探討如何極小化碳排放量與總延後時間，當多個工件所需要的容量空間不超過機台負荷時每一機台可以同時加工多個工件，由加工時間、到達時間、到期日與大小所定義出每一個工件的屬性並利用篩演算法的理念來求解。評估篩演算法的方式是透過求解多樣化且廣泛的測試題目來比較求解的時間與品質。實驗後的結果顯示，改良後的篩演算法之求解績效十分優異，相關研究成果可提供業者實務應用及後續相關學術研究的參考。

關鍵字

排程 ； 平行機 ； 批量 ； 碳排放量 ； 總延後時間 ； 篩演算法

並列摘要

This research aims to minimize the bi-criteria of Carbon Emission and total tardiness on a set of identical batch-processing machines arranged in parallel.Each machine can process multiple jobs simultaneously as long as the machine capacity is not exceeded.Each job is defined by its processing time,ready time,due date,and size.The processing time and ready time of a batch are represented by the largest processing time and release time among all jobs in the batch,respectively.For this problem,a scheduling algorithm based on the framework of the sieve algorithm was developed.Through extensive computational experiments with various problem instances, the effectiveness of the proposed algorithm was evaluated by measuring the computational efficiency and solution quality. The experiment results demonstrated that sieve algorithm had a superior performance compared to other benchmark algorithms, especially for large job instances.

並列關鍵字

Scheduling ； Batch-processing machine ； Carbon emission ； Total tardiness ； Sieve Algorithm

參考文獻

48. A. Chaudhuri and K. De, "Fuzzy Genetic Heuristic for University Course Timetable Problem,"International Journal of Advances in Soft Computing and its Application, Vol. 2, no. 1, 2010, pp. 2074-8523.

1. N. Gademann and S. Van de,"Batching to minimize total travel time in aparalle-aisle warehouse,"IIE Transactions, vol. 37,no. 1,2005,pp. 63-75.

2. A. J. R. M. Gademann, J. P. Vanden Berg and H. H. Van der Hoff, "An order batching algorithm for wave picking in a parallel-aisle warehouse,"IIE Transactions, vol. 33, 2001, pp. 385-398.

3. D. Qin, M. Manning and Z. Chen, Climate Change 2007: The Physical Science Basis, United Kingdom and New York, 2007.

5. R. Xu and H. Chen,"A bi-objective scheduling problem on batch machines via a Pareto-based ant colony system,"Int. J. Production Economics, vol. 145, 2013,pp.371-386.