﻿ 分布式估计算法在考虑差异工件的并行批处理机调度中的应用
 计算机系统应用  2019, Vol. 28 Issue (6): 213-220 PDF

Application of Estimation of Distribution Algorithm to Parallel Batch Processing Machines with Non-Identical Job Sizes
ZHANG Jian
School of Management, University of Science and Technology of China, Hefei 230026, China
Foundation item: National Natural Science Foundation of China (71671168)
Abstract: This paper aims at minimizing makespan of parallel batch processing machines with non-identical job sizes. All the jobs are grouped into batches within the restraint of machines’ capacity and then scheduled on the machines. First, a mixed integer programming model is summarized for this problem and a lower bound is proposed. Then an FF-LPT rule is addressed to form batches and assign batches on machines. And an estimation of distribution algorithm (EDA) with four different update mechanism is proposed. The performance of proposed algorithm is evaluated by comparing with a simulated annealing algorithm (SA) and a genetic algorithm (GA). The experimental results indicate that the effectiveness of proposed algorithm.
Key words: batch scheduling     parallel batch processing machines     estimation of distribution algorithm     non-identical job sizes

1 问题描述 1.1 数学模型

(1) 将n个工件分配到m个批处理机加工;

(2) 工件具有不同的尺寸和加工时间;

(3) 各台机器容量一致, 工件j只需在其中一台机器上加工, 且它在所有机器上加工时间相同;

(4) 工件集中分批, 按照批次顺序安排在机器上加工;

(5) 批的尺寸等于批中所有工件尺寸之和, 且不能超过机器容量限制, 批的加工时间等于批中工件最大加工时间;

(6) 一旦某个批次开始加工, 加工过程不能中断且不能有新的工件加入到当前批中;

(7) 优化目标是makespan, 也就是使最后离开加工 系统的批次的完工时间最小;

① 集合

② 参数

sj: 工件j尺寸;

pj: 工件j加工时间;

B: 机器容量;

③ 决策变量

PTbk: 在机器k上加工的批b的加工时间;

CTbk: 批b在机器k上的完工时间;

Cmax: 最终完工时间;

xjbk: 工件j分在批b中安排在机器k上加工时为1, 否则为0;

 $Minimise\;\;\;\;\;\;\;\;\;{C_{\max }}$ (1)
 ${\rm{s.t.}}\;\;\sum\limits_{b = 1}^n {\sum\limits_{k = 1}^m {{x_{jbk}}} } = 1,\;\;\;\;j = 1,\cdots,n$ (2)
 $\sum\limits_{j = 1}^n {{s_j}} {x_{jbk}} \le B,\;\;\;\;b \le n;\;k = 1,\cdots,m$ (3)
 $P{T_{bk}} \ge {p_j}{x_{jbk}},\;\;\;\;j = 1,\cdots,n;b \le n;\;k = 1,\cdots,m$ (4)
 $C{T_{bk}} = C{T_{b - 1,k}} + P{T_{bk}},\;\;\;\;b \le n;\;k = 1,\cdots,m$ (5)
 ${C_{\max }} \ge C{T_{bk}},\;\;\;\;b \le n;\;k = 1,\cdots,m$ (6)
 ${x_{jbk}} = \{ 0,\;1\} ,\;\;\;\;j = 1,\cdots,n;\;b \le \;n;\;k = 1,\cdots,m$ (7)

1.2 问题下界

 $LB\; = \;\sum\limits_{i = 1}^n {{s_i}{p_i}} /(m*B)$

2 分布式估计算法在考虑差异工件的并行批处理机调度中的应用 2.1 分布式估计算法

2.2 编码与解码

 图 1 EDA基本流程图

2.3 概率模型与更新机制

 图 2 10工件调度示意图

 ${{{P}}_{ij}}(t)\; = \;\left\{ {\begin{array}{*{20}{l}} {{p_{11}}(t)}& \cdots &{{p_{1n}}(t)}\\ {\;\; \vdots }& \ddots &{\;\; \vdots }\\ {{p_{n1}}(t)}& \cdots &{{p_{nn}}(t)} \end{array}} \right\}$

 $\begin{array}{l} fitness(i)\; = \;1.1\;*\max \{ {C_{\max }}(1),\cdots,{C_{\max }}(Q)\} \;{\rm{ - }}\;{C_{\max }}(i);\\ SP\_Size\;{\rm{ = }}\;\alpha \;{\rm{*}}\;Q \end{array}$

 $\begin{split} (1)\;&{p_{ij}}(t + 1) = (1 - \beta ){p_{ij}}(t) + \dfrac{\beta }{{SP\_Size}}\displaystyle\sum\limits_{k = 1}^{SP\_Size} {I_{ij}^k} \quad\quad\quad\quad\;\\ &I_{ij}^k = \left\{ \begin{array}{*{20}{l}} {1,\;\;\;\;\;\;\;\;if\text{工件}i\;\text{放在位置}j\;\text{上}}\\ {0,\;\;\;\;\;\;\;\;{\rm{otherwise}}} \end{array}\right. \end{split}$
 $\begin{split} (2)\;&{p_{ij}}(t + 1) = (1 - \beta ){p_{ij}}(t) + \dfrac{\beta }{{j*SP\_Size}}\displaystyle\sum\limits_{k = 1}^{SP\_Size} {I_{ij}^k}\quad\;\;\;\;\;\quad \\ &I_{ij}^k = \left\{ \begin{array}{*{20}{l}} {1,\;\;\;\;\;\;\;if\text{工件}i\;\text{放在位置}j\;\text{或之前位置}}\\ {0,\;\;\;\;\;\;{\rm{otherwise}}} \end{array}\right. \end{split}$
 $\begin{split} (3)\;&{p_{ij}}\left( {t + 1} \right) = \left( {1 - \beta } \right){p_{ij}}\left( t \right) + \dfrac{\beta }{{\left( {n - j + 1} \right)*SP\_Size}}\displaystyle\sum\limits_{k = 1}^{SP\_Size} {I_{ij}^k}\\ &I_{ij}^k = \left\{ \begin{array}{*{20}{l}} {1,\;\;\;\;\;\;\;\;if\text{工件}i\;\text{放在位置}j\;\text{或之后位置}}\\ {0,\;\;\;\;\;\;\;{\rm{otherwise}}} \end{array}\right. \end{split}$
 $\begin{split} (4)\;&{p_{ij}}(t + 1) = (1 - \beta ){p_{ij}}(t) + \dfrac{\beta }{{SP\_Size}}\displaystyle\sum\limits_{k = 1}^{SP\_Size} {\dfrac{{I_{ij}^k}}{{{\rm{|}}{v_j}{\rm{|}}}}} \quad\quad\quad\quad\\ &I_{ij}^k = \left\{ \begin{array}{*{20}{l}} {1,\;\;\;\;\;\;\;if\text{工件}i\;\text{放在位置}j\;\text{邻域范围内},}\\ \;\;\;\;\;\;\;\;\;\;{\text{邻域大小为}{\rm{|}}{v_j}{\rm{|}}}\\ {0,\;\;\;\;\;\;{\rm{otherwise}}} \end{array}\right. \end{split}$

 图 3 挑选的4个优势个体

2.4 面向差异工件的并行批处理机调度问题的分布式估计算法

t = 0 ;

While t < gen

t = t+1;

end

3 实验设计与结果分析 3.1 实验设计

 图 4 不同更新机制下优势个体概率矩阵计算结果

 ${\rm{ARV}} = \dfrac{{\displaystyle\sum\limits_{i = 1}^n {{C_{\max }}(i)/LB(i)} }}{n}$

3.2 实验结果及分析

 $ratio\;{\rm{ = }}\;ave({C_{\max }})/LB$

ratio越小, 说明结果越接近下界, 所得到的解越接近最优解.

 图 5 不同更新机制下EDA的因子水平趋势

 图 6 J2S2P1M1类典型算例收敛趋势图

4 结论与展望

 [1] Uzsoy R, Lee CY, Martin-Vega LA. A review of production planning and scheduling models in the semiconductor industry part Ⅱ: Shop-floor control. IIE Transactions, 1994, 26(5): 44-55. DOI:10.1080/07408179408966627 [2] Ghazvini FJ, Dupont L. Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes. International Journal of Production Economics, 1998, 55(3): 273-280. DOI:10.1016/S0925-5273(98)00067-X [3] 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 [4] 周盛超. 差异工件机器批调度若干问题研究[博士学位论文]. 合肥: 中国科学技术大学, 2016. [5] 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 [6] Lee CY, Uzsoy R, Martin-Vega LA. Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 1992, 40(4): 764-775. DOI:10.1287/opre.40.4.764 [7] 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 [8] Zhou SC, Chen HP, Xu R, et al. Minimising makespan on a single batch processing machine with dynamic job arrivals and non-identical job sizes. International Journal of Production Research, 2014, 52(8): 2258-2274. DOI:10.1080/00207543.2013.854937 [9] Chang PY, Damodaran P, Melouk S. Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 2004, 42(19): 4211-4220. DOI:10.1080/00207540410001711863 [10] Damodaran P, Chang PY. Heuristics to minimize makespan of parallel batch processing machines. The International Journal of Advanced Manufacturing Technology, 2008, 37(9–10): 1005-1013. [11] Chen HP, Du B, Huang GQ. Metaheuristics to minimise makespan on parallel batch processing machines with dynamic job arrivals. International Journal of Computer Integrated Manufacturing, 2010, 23(10): 942-956. DOI:10.1080/0951192X.2010.495137 [12] Xu R, Chen HP, Li XP. Makespan minimization on single batch-processing machine via ant colony optimization. Computers & Operations Research, 2012, 39(3): 582-593. [13] Xu SB, Bean JC. A genetic algorithm for scheduling parallel non-identical batch processing machines. Proceedings of 2007 IEEE Symposium on Computational Intelligence in Scheduling. Honolulu, HI, USA. 2007. 143–150. [14] Damodaran P, Diyadawagamage DA, Ghrayeb O, et al. A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines. The International Journal of Advanced Manufacturing Technology, 2012, 58(9–12): 1131-1140. [15] Zhou SC, Liu M, Chen HP, et al. An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes. International Journal of Production Economics, 2016, 179: 1-11. DOI:10.1016/j.ijpe.2016.05.014 [16] Zhou SC, Li XP, Chen HP, et al. Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm. International Journal of Production Research, 2016, 54(16): 4919-4937. DOI:10.1080/00207543.2016.1140920 [17] Aickelin U, Burke EK, Li J. An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering. Journal of the Operational Research Society, 2007, 58(12): 1574-1585. DOI:10.1057/palgrave.jors.2602308 [18] Pinedo ML. Scheduling: Theory, Algorithms, and Systems. 5th ed. Cham: Springer, 2016. [19] Mühlenbein H, Paaß G. From recombination of genes to the estimation of distributions I. Binary parameters. Proceedings of the 4th International Conference on Parallel Problem Solving from Nature. Berlin, Germany. 1996. 178–187.