具有共同到期日限制下最小化碳排放量之非相關平行機排程

過去針對非相關平行機排程的研究已提出許多種演算法求解，在取得最佳解的過程中，除了進行各演算法之探討及比較各績效指標之優劣外，也會加入許多限制條件來增加研究與現實之密切度；本研究沿用原始反覆貪婪演算法並加入FRB4指派方式做修改，求解具有共同到期日限制下最小化碳排放量之非相關平行機排程問題。文中除了解釋碳排放量如何運作及計算、共同到期日之參數水準的設定做說明外，亦探討其影響關係為何；本篇研究利用原始反覆貪婪法與修正型反覆貪婪法做出求解具有共同到期日限制下最小化碳排放量之非相關平行機排程問題的績效比較，依據所求出之數據，做詳盡的統計與分析。

關鍵字

非相關平行機；共同到期日；碳排放；最大完工時間；反覆貪婪演算法

並列摘要

With the crucial issue of environmental protection, managing natural resources efficiently and/or reducing the amount of carbon emissions have become more important than ever. In this paper, we focus on unrelated parallel machines with carbon emission problem given that the makespan does not exceed the common due date. We compare the original iterated greedy algorithm with modified iterated greedy algorithm to solve this problem. Finally, some computational results are provided.

並列關鍵字

scheduling ； unrelated parallel machines ； common due-date ； carbon emission

參考文獻

1. M. R. Garey, D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman, San Francisco, 1979.

2. R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, "Optimization and approximation in deterministic sequencing and scheduling: a survey," Annals of Discrete Mathematics, vol. 5, no. 8, 1979, pp. 287-326.

4. A. Allahverdi, J. Mittenthal, “Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time,” Naval Research Logistics, vol. 41, 1994, pp. 677-682.

5. T. C. E. Cheng, C. C. S. Sin, “A state-of-the-art review of parallel-machine scheduling research,” European Journal of Operational Research, vol. 47, no. 3, 1990, pp. 271-292.

6. W. C. Yeh, P. J. Lai, W. C. Lee, M. C. Chuang, “Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effects,” Information Sciences, vol. 269, no. 10, 2014, pp. 142-158.

國際替代計量

具有共同到期日限制下最小化碳排放量之非相關平行機排程

全文下載

主題瀏覽