考虑分时电价的多目标批调度问题蚁群算法求解

中国管理科学 ›› 2014, Vol. 22 ›› Issue (12): 56-64.

考虑分时电价的多目标批调度问题蚁群算法求解

李小林¹, 张松², 陈华平²

1. 中国矿业大学矿业工程学院, 江苏徐州 221116;
2. 中国科学技术大学管理学院, 安徽合肥 230026

收稿日期:2012-03-19 修回日期:2013-05-14 出版日期:2014-12-20 发布日期:2014-12-23
作者简介:李小林(1986-),男(汉族),江苏徐州人,中国矿业大学矿业工程学院,讲师,研究方向:智能优化算法、信息系统.
基金资助:
创新研究群体科学基金资助项目(70821001);国家自然基金资助项目(71171184);中国矿业大学青年科技基金项目(2014QNA48);国家自然科学青年基金项目(71401164)

Solving Multi-objective Batch Scheduling Under TOU Price Using Ant Colony Optimization

LI Xiao-lin¹, ZHANG Song², CHEN Hua-ping²

1. School of Mines, China University of Mining and Technology, Xuzhou 221116, China;
2. School of Management, University of Science and Technology of China, Hefei 230026, China

Received:2012-03-19 Revised:2013-05-14 Online:2014-12-20 Published:2014-12-23

摘要/Abstract

摘要： 对同时优化电力成本和制造跨度的多目标批处理机调度问题进行了研究,设计了两种多目标蚁群算法,基于工件序的多目标蚁群算法(J-PACO,Job-based Pareto Ant Colony Optimization)和基于成批的多目标蚁群算法(B-PACO,Batch-based Pareto Ant Colony Optimization)对问题进行求解分析。由于分时电价中电价是时间的函数,因而在传统批调度进行批排序的基础上,需要进一步确定批加工时间点以测定电力成本。提出的两种蚁群算法分别将工件和批与时间线相结合进行调度对此类问题进行求解。通过仿真实验将两种算法对问题的求解进行了比较,仿真实验表明B-PACO算法通过结合FFLPT(First Fit Longest Processing Time)启发式算法先将工件成批再生成最终方案,提高了算法搜索效率,并且在衡量算法搜索非支配解数量的Q指标和衡量非支配集与Pareto边界接近程度的HV指标上,均优于J-PACO算法。

关键词: 多目标, 调度, 蚁群算法, 批处理机, 分时电价

Abstract: The problem of scheduling batch processing machines is considered in this study. Batch processing machines are encountered in various manufacturing environment and the study is motivated by burning-in operation in semiconductor manufacturing while time-of-use electricity price is considered as well. In the problem under study, jobs seizes are non-identical and machines are batch processing machines which can process several jobs simultaneously as a batch.Since the electricity price is time related, the objectives of electrical cost and makespan is influenced by start processing time of each batch. These two objectives were minimized simultaneously on single batch processing machine with non-identical job sizes. Two pareto ant colony optimization algorithms were designed to solve the problem. One is J-PACO (Job-based Pareto Ant Colony Optimization) algorithm and the other is B-PACO (Batch-based Ant Colony Optimization) algorithm. This problem is different from traditional batch scheduling problems. As the price is related to the time, the start processing time of jobs should be determined after the sequence of batches are fixed. In the two algorithms proposed, jobs and batches are scheduled on time line separately. Random job instances are generated in the simulation experimentation to evaluate the performance of algorithms proposed. The experiment results indicate that B-PACO, which group jobs into batches using FFLPT(First Fit Longest Processing Time), outperforms J-PACO in computational time, numbers of non-dominated solution and hypervolume. The study will be helpful in the application of ACO involving multi objectives. And, the idea of allocating jobs in a time line before they are grouped into batches can also be used in scheduling batch processing machines.

Key words: multi-objective, scheduling, ant colony optimization, batch processing machine, TOU price

中图分类号:

TP301

李小林, 张松, 陈华平. 考虑分时电价的多目标批调度问题蚁群算法求解[J]. 中国管理科学, 2014, 22(12): 56-64.

LI Xiao-lin, ZHANG Song, CHEN Hua-ping. Solving Multi-objective Batch Scheduling Under TOU Price Using Ant Colony Optimization[J]. Chinese Journal of Management Science, 2014, 22(12): 56-64.

参考文献

[1] Ahmadi J H, Ahmadi R H,Dasu S, et al. Batching and scheduling jobs on batch and discrete processors[J]. Operations Research, 1992, 40(4): 750-763.

[2] Ikura Y, Gimple M. Efficient scheduling algorithms for a single batch processing machine[J]. Operations Research Letters, 1986, 5(2):61-65.

[3] Uzsoy R. Scheduling a single batch processing machine with nonidentical job sizes[J]. International Journal of Production Research, 1994, 32(7): 1615-1635.

[4] Dupont L, Ghazvini F J. Minimizing makespan on a single batch processing machine with non-identical job sizes[J]. APII-JESA Journal Europeen des Systemes Automatises, 1998, 32(4): 431-440.

[5] Dupont L, Dhaenens-Flipo C. Minimizing the makespan on a batch machine with non-identical job sizes: An exact procedure[J]. Computers & Operations Research, 2002, 29(7): 807-819.

[6] Brucker P, Kovalyov M Y. Single machine batch scheduling to minimize the weighted number of late jobs[J]. ZOR-Mathematical Methods of Operations Research, 1996, 43(1): 1-88.

[7] Uzsoy R, Yang Yaoyu. Minimizing total weighted completion time on a single batch processing machine[J]. Production and Operations Management, 1997, 6(1):57-73.

[8] Melouk S, Damodaran P, Chang Pingyu. Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing [J]. International Journal of Production Economics, 2004, 87(2):141-147.

[9] Damodaran P, Manjeshwar P K, Srihari K. Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms [J]. International Journal of Production Economics, 2006,103(2): 882-891.

[10] Kashanl A H, Karimi B, Jolai F. Minimizing makespan on a single batch processing machine with non-identical job sizes: A hybrid genetic approach[M].// Raidl J G G R. Evolutionary Computation in Combinatorial Optimization. Springer-Verlag Berlin: Berlin,2006: 135-146.

[11] 王栓狮, 陈华平,程八一,等. 一种差异工件单机批调度问题的蚁群优化算法[J]. 管理科学学报, 2009, 12(6): 72-82.

[12] 杜冰, 陈华平,程八一,等. 具有不同到达时间的差异工件批调度问题的蚁群聚类算法[J]. 系统工程理论与实践, 201030(9): 1701-1709.

[13] 程八一, 陈华平, 王栓狮, 基于微粒群算法的单机不同尺寸工件批调度问题求解[J]. 中国管理科学, 2008, 16(3): 84-88.

[14] Kashan A H, Karimi B, Jolai F. An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes [J]. Engineering Applications of Artificial Intelligence, 2010, 23(6):911-922.

[15] Potts C N, Kovalyov M Y. Scheduling with batching: A review [J]. European Journal of Operational Research, 2000, 120(2): 228-249.

[16] Lei Deming. Multi-objective production scheduling: a survey [J]. International Journal of Advanced Manufacturing Technology, 2009, 43(9-10): 926-938.

[17] Jaszkiewicz A. Genetic local search for multi-objective combinatorial optimization[J]. European Journal of Operational Research, 2002, 137(1): 50-71.

[18] Johnson D S,Demers A,Ullman J D, et al. Worst-case performance bounds for simple one-dimensional packing algorithms[J]. SIAM Journal on Computing, 1974, 3(4): 299-325.

[19] Zitzler E, Thiele L. Multiobjective optimization using evolutionary algorithms- A comparative case study[M]//E:ben A E. Parallel problem solving from nature- Ppsn V. Berlin:Springer-Verlag Berlin,1998: 292-301.