﻿ 遗传算法在考虑能耗的单机批调度中的应用
 计算机系统应用  2018, Vol. 27 Issue (8): 138-145 PDF

Application of Genetic Algorithm to Single Machine Batch Scheduling Problem with Energy Cost Consideration
WU Chou
School of Management, University of Science and Technology of China, Hefei 230026, China
Foundation item: National Natural Science Foundation of China (71671168)
Abstract: Energy cost has become a critical factor in production scheduling where trade-off between makespan and total energy consumption should be considered. In this study the genetic algorithm is applied to the single machine batch scheduling problem with energy cost consideration and a model which simultaneously optimizes the makespan and total energy cost was proposed. By using the genetic algorithm, a set of non-dominated solutions are obtained in the situation of Considering Energy Consumption (CEC) and Ignoring Energy Consumption (ICE) respectively and the algorithm’s efficiency was guaranteed by optimizing the batch and improving the selection of the genetic operators. The experimental results show that the solution is obtained under the CEC has better effectiveness than that under the IEC. Moreover, the performance of CEC is getting better obviously when the problem size and job power increase.
Key words: genetic algorithm     batch scheduling     energy consumption     non-identical job size

1 问题描述 1.1 相关定义

 图 1 状态转换过程

1.2 数学模型 1.2.1 假设和约束

(1) 工件集合 ${{J}} = \{ 1,2, \cdots, N\}$ , 工件j的加工时间 ${p_j}$ , 尺寸 ${s_j}$ , 加工功率 ${e_j}$ .

(2) J中工件分批加工, 任一批中的工件集合 ${{{B}}^b}$ , 其中工件总尺寸和不超过机器容量C.

(3) 加工不允许中断, 批b的加工时间 ${P^b}$ ${B^b}$ 中所有工件最大加工时间, 批b的功率 ${E^b}$ ${B^b}$ 中所有工件的最大加工功率.

(4) 目标是如何安排生产, 使得 ${C_{\max }}$ 最小和TEC最少.

1.2.2 数学表达式形式

(1) 集合

J: 工件集合 $J = \{ 1,2, \cdots, N\}$ .

B: 批次集合 $B = \{ {b_1},{b_2}, \cdots, {b_m}\}$ .

T: 单位时间集合 $T = \{ {t_1},{t_2}, \cdots, {t_n}\}$ .

S: 机器状态集合, S={1,2,3}, 1表示加工, 2表示待机, 3表示关机.

(2) 参数

${c_t}$ : t时刻单位电价.

${E_s}$ : 机器为状态s时的单位功率.

${E_{s{s'}}}$ : 机器状态转换的单位功率.

${T_{s{s'}}}$ : 机器状态转换的时间.

${p_j}$ : 工件加工时间.

${P^b}$ : 批的加工时间.

${E^b}$ : 批的加工功率.

$s{t^b}$ : 批的开始时间.

$c{t^b}$ : 批的完成时间.

$y_j^b$ : 工件jb批中时 $y_j^b{\rm{ = }}1$ , 反之 $y_j^b{\rm{ = 0}}$ .

$s_b^t$ : 批bt开始加工时 $s_b^t{\rm{ = }}1$ , 反之 $s_b^t{\rm{ = }}0$ .

$\chi _b^t$ : 批bt处于加工状态时 $\chi _b^t$ =1, 反之 $\chi _b^t$ =0.

$\alpha _s^t$ : 机器t处于s状态时 $\alpha _s^t$ =1, 反之 $\alpha _s^t$ =0.

$\beta _{s{s'}}^t$ : 机器t处于转换过程时 $\beta _{s{s'}}^t$ =1, 反之 $\beta _{s{s'}}^t$ =0.

(3) 问题的数学模型

 $Min{C_{\max }}$ (1)
 $Min\sum\limits_{t \in T} {{c_t}[\sum\limits_{b \in B} {{E^b}} \chi _b^t + \sum\limits_{s = 2} {{E_s}} \alpha _s^t + \sum\limits_{s,{s'} \in S} {{E_{s{s'}}}} \beta _{s{s'}}^t]}$ (2)
 ${\rm{s.t.}}\;\;\;\sum\limits_{b \in B} {y_j^b = 1,\;\;j \in J}$ (3)
 $\sum\limits_{j = 1}^N {{s_j}} y_j^b \leqslant C,\;\;b \in B$ (4)
 ${P^b} = \max\{ {p_j}y_j^b\} ,\;\;j \in J,b \in B$ (5)
 ${E^b} = \max\{ {e_{\rm{j}}}y_j^b\} ,\;\;j \in J,b \in B$ (6)
 $\sum\limits_{j = 1}^N {\frac{{{s_j}}}{C}} \leqslant m \leqslant N$ (7)
 $\sum\limits_{b \in B} {\chi _b^t} \leqslant 1,\;\;t \in T$ (8)
 $t \geqslant s{t^b} - (1 - \chi _b^t){P^b},\;\;b \in B$ (9)
 $t \leqslant c{t^b} - 1 + (1 - \chi _b^t){P^b},\;\;b \in B$ (10)
 $\sum\limits_{b \in B} {\chi _b^t} = \alpha _1^t,\;\;t \in T$ (11)
 $\sum\limits_{s \in S} {\alpha _s^t} + \sum\limits_{s,{s'} \in S} {\beta _{s{s'}}^t} = 1,\;\;t \in T$ (12)
 $\alpha _s^t \leqslant \sum\limits_{{s'} \in S,{T_{s{s'}}} = 0} {\alpha _{{s'}}^{t + 1} + \sum\limits_{{s^{''}} \in S,{T_{s{s^{''}}}} \geqslant 1} {\beta _{s{s^{''}}}^{t + 1}} } ,\;t \in T,t \ne card(T)$ (13)
 $\beta _{s{s'}}^t \leqslant \beta _{s{s'}}^{t + 1} + \alpha _{{s'}}^{t + 1},\;\;t \in T,s \in S,{s'} \in S,{T_{ss'}} \geqslant 1$ (14)
 \begin{aligned} s_{{b'}}^{{t'}} \leqslant \sum\limits_{{t'} \leqslant t} {s_b^t} ,\;&{b} = 1,2, \cdots, m,\;b' = 1,2, \cdots, m,\;{b'} \leqslant b,\\ & {t} \in T,t' \in T\end{aligned} (15)

2 遗传算法在考虑能耗的单机批调度中的应用 2.1 编码与初始种群的产生

2.2 目标的评估

${C_{\max }}$ 为最后一批工件加工结束的时间, ${C_{\max }}$ 越小意味着机器的利用率越高. 在生产过程中使用随着时间变化的价格可能会给制造企业在成本上带来一定程度的节约, Nghiem等[14]通过对减少峰值的能耗需求的控制系统的绿色调度进行研究, 并证明抑制峰值能够使成本和效率之间更加协调, 所以本文最小化TEC主要是通过延长 ${C_{\max }}$ 来降低能耗成本, 比如在用电高峰(单位电价较高)时等待或者关闭机器, 选择单位电价比较合理时(用电低峰)进行工件加工.

 \left\{\begin{aligned}&{c_{{t'}}} \geqslant {c_{{t'} + 1}}\\&P{E_{\rm{idle}}}\sum\limits_{t = {t'}}^{t + {T_{\rm{idle}}}} {{c_t}} + {E^b}\sum\limits_{t = {t'} + {T_{\rm{idle}}}}^{t + {T^b}} {{c_t}} \leqslant {E^b}\sum\limits_{t = {t'}}^{t + {T^b}} {{c_t}}\end{aligned}\right. (16)
 \left\{\begin{aligned}&{T_{\rm{idle}}} \! \geqslant \! {T_{\rm{on}}}\! +\! {T_{\rm{off}}}\\&P{E_{\rm{idle}}}\sum\limits_{t \in {T_{\rm{idle}}}} {{c_t}} \!\geqslant\! P{E_{\rm{on}}}\!\! \sum\limits_{t \in {T_{\rm{on}}}} {{c_t}} \!+\! P{E_{\rm{off}}} \!\! \sum\limits_{t \in {T_{\rm{off}}}} {{c_t}}\end{aligned} \right. (17)
2.3 工件分批及其优化

(1) K为总批数, k=K.

(2) 如果k<2, 程序结束, 反之h=k-1.

(3) 如果 $h \geqslant 1$ , 找到 ${B^k}$ 中加工时间最长的工件a, 即 ${p_a} = {P^k}$ , ${B^h}$ 的剩余空间 $s{c^h}$ , ${B^k}$ 的剩余空间 $s{c^k}$ , 如果 ${p_a} > {P^h}$ , $h = h - 1$ ; 如果 ${p_a} \leqslant {P^h}$ ${s_a} \leqslant s{c^h}$ , 把工件a ${B^k}$ 移到 ${B^h}$ 中, 更新批次; 如果 ${p_a} \leqslant {P^h}$ ${s_a} \geqslant s{c^h}$ , 跳转(4). 反之k=k–1, 跳转(2).

(4) 找到 ${B^h}$ 中满足 ${p_i} < {p_a}$ 的工件集合 $\omega$ , $\omega=$ $\{ i \in {B^h}|{p_i} < {p_a}\}$ , $\;\omega \in {B^h}$ 计算 $\omega$ 中所有工件的尺寸 $s(\omega )$ . 如果 ${B^k}$ 中工件a满足 $s(\omega ) \leqslant s{c^k} + {s_a}$ ${s_a} \leqslant s{c^h} + s(\omega )$ , 工件a和集合 $\omega$ 中所有工件交换, 否则删除集合 $\omega$ 中最后一个工件直到集合 $\omega {\rm{ = }}\emptyset$ .

2.4 适应度的计算

${G^i}$ 表示个体 $i$ 优于其它个体的数目, 定义如下:

 \begin{aligned}&{G^i} = \sum\limits_{j = 1}^{PopSize} {{m_j}}\\&\left\{ {\begin{array}{*{20}{c}} {{m_j} = 1}&{j \prec i,i \ne j} \\ {{m_j} = 0}&{\rm{otherwise}} \end{array}} \right.\end{aligned} (18)

${S^i}$ 表示严格优于自己的所有个体的长度值 ${G^i}$ 之和, 具体定义为:

 ${S^i} = \sum\limits_{j = 1}^{PopSize} {{G^j}} ,\;\;\forall i \prec j$ (19)

 ${\omega _i} = \sqrt {{{\left( {C_{\max }^{'i} - C_{\max }^{'j}} \right)}^2} + {{(TE{C^{'i}} - TE{C^{'j}})}^2}}$ (20)

$\omega _i^k$ ${\omega _i}$ 升序排列的第 $k$ 个值, $k = \sqrt {PopSize}$ , 密度估计定义为:

 ${d_i} = \frac{1}{{\omega _{_i}^k + 2}},\;\;0 < {d_i} < 1$ (21)
2.5 最优解的选择

(1) 对种群中的所有个体计算适应度值, 并将个体按从小到大的适应度值排列, 记为 ${S_1}$ .

(2) 根据选择概率轮盘赌选择个体, 并按选中的顺序排好序, 记为 ${S_2}$ .

(3) 根据 ${S_2}$ 的结果判断哪些个体被选中的次数超过种群的20%, 找到这些个体对应的原个体, 即对应位置上的 ${S_1}$ 中的个体, 除了第一次出现的位置不进行处理, 其余的位置通过Metropolis准则来判断该个体是被接受还是舍弃, 处理过程为:

1) i ${S_1}$ 中的个体, j ${S_2}$ 中对应位置的个体.

2) 当 ${F^i} > {F^j}$ , 产生随机数 $r \in (0,1)$ , 当满足条件 $r \leqslant \exp \{ ({F^j} - {F^i})/T\}$ 时, 保留 ${S_2}$ 中的个体j, 否则用个体i代替个体j, 其中T为控制参数.

3) 当 ${F^i} < {F^j}$ 时, 对 ${S_2}$ 中的个体j进行保留.

(4) ${S_2}$ 为最后选中的个体.

3 仿真实验与分析 3.1 实验设计

 $c(t) = \left\{ {\begin{array}{*{20}{c}} 5,&{24n - 3 \leqslant t < 24n + 7} \\ 8,&{24n + 7 \leqslant t < 24n + 11} \\ {10},&{24n + 11 \leqslant t < 24n + 17} \\ 8,&{24n + 17 \leqslant t < 24n + 21} \end{array}} \right.$ (22)

(1)解的质量用Pareto最优解集规模表示, Pareto最优解集规模为找到非支配解的数量, 解的数目越多, 选择余地更多.

(2)用解集之间的覆盖率来对算法性能进行衡量, 覆盖率C(A,B)表示算法B所求得的Pareto最优解集被算法A所生成解集支配的解的比例, 按照下式计算:

 $C{\kern 1pt} {\kern 1pt} (A,B) = \frac{{|\{ b \in B|\exists a \in A:a \succ b{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{or}}{\kern 1pt} {\kern 1pt} a = b\} |}}{{|B|}}$ (23)

3.2 实验结果与分析

 图 2 10个工件问题的非支配解分布图

 图 3 20个工件问题的非支配解分布图

 图 4 50个工件问题的非支配解分布图

 图 5 算例J1p1s1e1的迭代优化图

 图 6 算例J2p1s2e2的迭代优化图

 图 7 算例J3p2s3e3的迭代优化图

4 结论

 [1] Taylor P, Francoeur M, d’Ortigue OL, et al. Worldwide trends in energy use and efficiency: Key insights from IEA indicator analysis. IEEJ Workshop. Tokyo, Japan. 2008. [2] Ikura Y, Gimple M. Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters, 1986, 5(2): 61-65. DOI:10.1016/0167-6377(86)90104-5 [3] Uzsoy R. Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 1994, 32(7): 1615-1635. DOI:10.1080/00207549408957026 [4] Pechmann A, Schöler I. Optimizing energy costs by intelligent production scheduling. In: Hesselbach J, Herrmann C, eds. Glocalized Solutions for Sustainability in Manufacturing. Berlin, Heidelberg: Springer, 2011. 293–298. [5] Yu W, Li BZ, Jia HY, et al. Application of multi-objective genetic algorithm to optimize energy efficiency and thermal comfort in building design. Energy and Buildings, 2015, 88: 135-143. DOI:10.1016/j.enbuild.2014.11.063 [6] Gong X, De Pessemier T, Joseph W, et al. A generic method for energy-efficient and energy-cost-effective production at the unit process level. Journal of Cleaner Production, 2016, 113: 508-522. DOI:10.1016/j.jclepro.2015.09.020 [7] Melouk S, Damodaran P, Chang PY. Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. International Journal of Production Economics, 2004, 87(2): 141-147. DOI:10.1016/S0925-5273(03)00092-6 [8] Damodaran P, Manjeshwar PK, Srihari K. Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms. International Journal of Production Economics, 2006, 103(2): 882-891. DOI:10.1016/j.ijpe.2006.02.010 [9] Shrouf F, Ordieres-Meré J, García-Sánchez A, et al. Optimizing the production scheduling of a single machine to minimize total energy consumption costs. Journal of Cleaner Production, 2014, 67: 197-207. DOI:10.1016/j.jclepro.2013.12.024 [10] Che A, Zeng YZ, Lyu K. An efficient greedy insertion heuristic for energy-conscious single machine scheduling problem under time-of-use electricity tariffs. Journal of Cleaner Production, 2016, 129: 565-577. DOI:10.1016/j.jclepro.2016.03.150 [11] Oron D. Scheduling a batching machine with convex resource consumption functions. Information Processing Letters, 2011, 111(19): 962-967. DOI:10.1016/j.ipl.2011.07.005 [12] Liu GS, Zhang BX, Yang HD, et al. A branch-and-bound algorithm for minimizing the energy consumption in the PFS problem. Mathematical Problems in Engineering, 2013, 2013: 546810. [13] May G, Taisch M, Stahl B, et al. Toward energy efficient manufacturing: A study on practices and viewpoint of the industry. In: Emmanouilidis C, Taisch M, Kiritsis D, eds. IFIP International Conference on Advances in Production Management Systems. Berlin Heidelberg: Springer, 2012. 1–8. [14] Nghiem TX, Behl M, Mangharam R, et al. Green scheduling of control systems for peak demand reduction. Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC). Orlando, FL, USA. 2011. 5131–5136. [15] May G, Stahl B, Taisch M, et al. Multi-objective genetic algorithm for energy-efficient job shop scheduling. International Journal of Production Research, 2015, 53(23): 7071-7089. DOI:10.1080/00207543.2015.1005248