分布式估计算法在考虑差异工件的并行批处理机调度中的应用
|
摘要
论文考虑包含差异工件的并行批处理机调度问题,优化目标是最小化制造跨度.在不违背机器容量的限制下,所有工件需要被分成不同的批次,然后被安排在机器上进行加工.首先根据问题提出一个混合整数规划模型,并提出一个下界;采用FF-LPT规则实现对工件的分批和排序;然后提出基于4种更新机制的分布式估计算法(EDA)来对问题求解.最后通过实验对各类规模不同的算例进行仿真,并将结果和模拟退火算法(SA)、遗传算法(GA)作对比,验证了算法的有效性.
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.
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.
引文
1 Uzsoy R, Lee CY, Martin-Vega LA. A review of production planning and scheduling models in the semiconductor industry part II:Shop-floor control. IHE 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 of2007 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 Muhlenbein 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.
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 of2007 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 Muhlenbein 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.