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

中国管理科学 ›› 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.

相关文章 15

[1]	何一丹,何正文,王能民,马志强. 共享经济环境下的资源约束Max-NPV多项目调度优化[J]. 中国管理科学, 2024, 32(9): 260-270.
[2]	周林,黄鹏,代应,宋寒. 区域互救与外部救助耦合的突发性疫情初期应急物资协同调度研究[J]. 中国管理科学, 2024, 32(8): 297-307.
[3]	李铁克,苏艺璇,张文新,王柏琳. 加工时间不确定的炼钢-连铸区间多目标优化调度[J]. 中国管理科学, 2024, 32(8): 95-106.
[4]	初梓豪,徐哲,刘东宁. 带有活动重叠的随机调度问题建模与算法研究[J]. 中国管理科学, 2024, 32(7): 84-94.
[5]	汪和平,赵登宇,陈梦凯,李艳. 基于MO-CGJaya/D算法的PC构件混流生产作业指派优化研究[J]. 中国管理科学, 2024, 32(7): 95-105.
[6]	李陆苗,周鹏,李整军,刘嘉赓. 考虑分时电价与光伏出力关系的分布式光伏投资决策研究[J]. 中国管理科学, 2024, 32(5): 179-186.
[7]	王付宇,谢昊轩,林钟高,王骏. 突发事件下高铁站应急疏散多目标优化模型与自适应量子蚁群算法[J]. 中国管理科学, 2024, 32(3): 188-197.
[8]	黄肖玲,李壮壮. 基于柔性生产机制的“前港后厂”港口取料机应急调度优化[J]. 中国管理科学, 2024, 32(3): 210-217.
[9]	陈雪龙,张钟,李悦. 临机决策视角下的非常规突发事件应急处置方案生成[J]. 中国管理科学, 2024, 32(10): 109-122.
[10]	李惠,王熙,左治亚. 多目标下航天产品生产车间柔性资源配置与调度集成优化[J]. 中国管理科学, 2024, 32(10): 146-155.
[11]	乔岩,冉伦,李金林,王志远. 基于两阶段随机规划的远程会诊预约调度问题研究[J]. 中国管理科学, 2024, 32(1): 86-93.
[12]	黄丽,叶春明,郭鹏. 基于韧性城市视角的突发事件下分布式应急手术调度研究[J]. 中国管理科学, 2024, 32(1): 94-105.
[13]	王海宇. 基于简单检测方法的动态 $n p x$ 控制图的经济统计优化设计[J]. 中国管理科学, 2023, 31(9): 205-213.
[14]	赵松,徐哲,刘东宁. 地域分散型多项目时间/成本权衡问题[J]. 中国管理科学, 2023, 31(9): 62-72.
[15]	崔维伟,刘新波. 多源供电模式下企业生产运作与能源管理集成优化研究[J]. 中国管理科学, 2023, 31(8): 173-183.