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

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

作　　者：李小林[1] 张松[2] 陈华平[2] 

机构地区：[1]中国矿业大学矿业工程学院,江苏徐州221116 [2]中国科学技术大学管理学院,安徽合肥230026

出　　处：《中国管理科学》2014年第12期56-64,共9页Chinese Journal of Management Science

基　　金：创新研究群体科学基金资助项目(70821001);国家自然基金资助项目(71171184);中国矿业大学青年科技基金项目(2014QNA48);国家自然科学青年基金项目(71401164)

摘　　要：对同时优化电力成本和制造跨度的多目标批处理机调度问题进行了研究,设计了两种多目标蚁群算法,基于工件序的多目标蚁群算法(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算法。"The problem of scheduling batch processing machines is considered in this study. Batch process- ing 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 e- lectrical 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） algo- rithm. 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 ex- periment 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 i- dea of allocating jobs in a time line before they are grouped into batches can also be used in scheduling batch processing machines.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]