The Energy-Efficient Flexible Job-Shop Scheduling Problem

有效節能之彈性零工式排程問題

楊逸旋(Yi-Hsuan Yang)

指導教授 ： 林永隆

國立清華大學/電機資訊學院/資訊工程學系/碩士(2011年)

https://doi.org/10.6843/NTHU.2011.00508

摘要

在此論文當中，我們研究了一個新的彈性零工式排程的新問題，名為「有效節能之彈性零工式排程問題」。近年來，由於如何有效的利用能源日趨重要，因此我們研究的目標為如何在給定的時間限制內使總能量消耗值最小化。為了進一步減少耗能，我們改善且加強了原先問題當中機器的定義─機器不但是多功能的，每部機器尚能以多樣的速度模式運作，伴隨著不同功率的消耗。在一個時間限制下，使用以低耗能模式運作的機器對能量減少總是十分有利的。我們採用整數線性規劃來使總消耗能量之值最佳化，同時解決如何安置操作於機器以及操作的先後順序關係。研究實驗結果顯示，提出的演算法確實在減少能量方面十分有效。

關鍵字

彈性零工式排程問題 ； 有效節能 ； 整數線性規劃

並列摘要

In this thesis, we study a new Flexible Job−Shop Scheduling Problem (FJSP) named Energy−Efficient Flexible Job−Shop Scheduling Problem (EEFJSP). Our goal is to minimize the total energy consumption under a makespan constraint. In our problem, machines are multi−functional and each machine may run in various speed modes consuming different amount of power. Within a time constraint, it is always beneficial to use a machine running in a low power mode. We employ an ILP−based approach for machine assignment and operation sequencing under a makespan constraint while minimizing total energy consumption. Experimental results show that the proposed algorithm is indeed effective for energy minimization.

並列關鍵字

Flexible job-shop scheduling problem ； Energy-efficient ； Integer linear programming

參考文獻

[1] P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Annals of Operations Research, vol. 41, no. 3, pp. 157–183, 1993.

[2] I. Kacem, S. Hammadi, and P. Borne, “Approach by localization and multiobjective evolutionary optimization for flexible job−shop scheduling problems,” IEEE Transactions on systems, man, and cybernetics, Part C, vol. 32, no. 1, pp. 1–13, 2002a.

[3] I. Kacem, S. Hammadi, and P. Borne, “Pareto−optimality approach for flexible job−shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic,” Mathematics and Computers in Simulation, vol. 60, pp. 245–276, 2002b.

[4] W. Xia and Z. Wu, “An effective hybrid optimization approach for multi−objective flexible job−shop scheduling problems,” Computers and Industrial Engineering, vol. 48, no. 2, pp. 409–425, 2005.

[5] G. Zhang, X. Shao, P. Li, and L. Gao, “An effective hybrid particle swarm optimization algorithm for multi−objective flexible job−shop scheduling problem,” Computers and Industrial Engineering, vol. 56, pp. 1309–1318, 2009.