《计算机应用研究》|Application Research of Computers

求解并行机拖期与能耗成本优化调度的混合教—学算法

Hybrid teaching-learning-based optimization algorithm for optimizing tardiness and energy cost on parallel machine scheduling

免费全文下载 (已被下载 次)  
获取PDF全文
作者 王永琦,吴飞,江潇潇,王春媛
机构 上海工程技术大学 电子电气工程学院,上海 201620
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2019)03-006-0673-04
DOI 10.19734/j.issn.1001-3695.2017.09.0929
摘要 针对加工时间可控的并行机调度,提出了一类考虑拖期与能耗成本优化的调度问题。首先对调度问题进行了问题描述,并建立了整数线性规划模型以便于CPLEX求解。为了快速获得问题的满意解,提出了一种混合教—学算法。结合问题的性质,设计了编码与解码方法以克服标准教—学算法无法直接适用于离散问题的缺点。同时,构建了基于变邻域搜索的局部搜索算子以强化混合算法的搜索性能。最后,对加工时间可控的并行机调度问题进行了仿真实验,测试结果验证了构建的整数线性规划模型和混合算法的可行性和有效性。
关键词 并行机调度;拖期;能耗;可控加工时间;教—学优化算法
基金项目 国家自然科学基金资助项目(F020207)
上海市科委资助项目(13510501400)
国家自然科学基金项目(61701295)
本文URL http://www.arocmag.com/article/01-2019-03-006.html
英文标题 Hybrid teaching-learning-based optimization algorithm for optimizing tardiness and energy cost on parallel machine scheduling
作者英文名 Wang Yongqi, Wu Fei, Jiang Xiaoxiao, Wang Chunyuan
机构英文名 SchoolofElectronic&ElectricalEngineering,ShanghaiUniversityofEngineering,Shanghai201620,China
英文摘要 For the parallel machine scheduling with controllable processing times (PMS-CPT) , this paper proposed a scheduling problem for optimizing tardiness and energy cost. First, this article developed an integer linear programming (ILP) model for the proposed scheduling problem in order to facilitate the CPLEX solver. Second, it established a hybrid teaching-learning-based optimization (HTLBO) algorithm to quickly obtain satisfactory solutions. This algorithm adopted a new coding and decoding method according to the nature of the proposed parallel machine scheduling problem, which overcame the weakness of standard teaching-learning-based optimization algorithm that could not be directly applied to discrete problems. Meanwhile, it also proposed a local optimizer based on variable neighborhood search (VNS), which aimed to enhance the performance of the hybrid algorithm. Finally, it conducted the simulations to solve instances of PMS-CPT. The experimental results demonstrate the feasibility and validity of the proposed ILP model and hybrid algorithm.
英文关键词 parallel machine scheduling; tardiness; energy; controllable processing times; teaching-learning-based optimization algorithm
参考文献 查看稿件参考文献
  [1] Cheng T C E, Sin C C S. A state-of-the-art review of parallel-machine scheduling research[J] . European Journal of Operational Research, 1990, 47(3):271-292.
[2] Adamu M O, Abass O. Parallel machine scheduling to maximize the weighted number of just-in-time jobs[J] . Journal of Applied Scien-ce and Technology, 2010, 15(1-2).
[3] Yin Yunqiang, Cheng S R, Cheng T C E, et al. Just-in-time scheduling with two competing agents on unrelated parallel machines[J] . Omega, 2016, 63(9):41-47.
[4] Li Kai, Zhang Xun, Leung J Y T, et al. Parallel machine scheduling problems in green manufacturing industry[J] . Journal of Manufacturing Systems, 2016, 38(1):98-106.
[5] Lin Y K, Pfund M E, Fowler J W. Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems[J] . Computers & Operations Research, 2011, 38(6):901-916.
[6] Balin S. Non-identical parallel machine scheduling using genetic algorithm[J] . Expert Systems with Applications, 2011, 38(6):6814-6821.
[7] Rao R V, Savsani V J, Vakharia D P. Teaching-learning-based optimization:an optimization method for continuous non-linear large scale problems[J] . Information Sciences, 2012, 183(1):1-15.
[8] Rao R V, Patel V. An improved teaching-learning-based optimization algorithm for solving unconstrained optimization problems[J] . Scientia Iranica, 2013, 20(3):710-720.
[9] 高立群, 欧阳海滨, 孔祥勇, 等. 带有交叉操作的教—学优化算法[J] . 东北大学学报:自然科学版, 2014, 35(3):323-327. (Gao Liqun, Ouyang Haibin, Kong Xiangyong, et al. Teaching-learning based optimization algorithm with crossover operation[J] . Journal of Northeastern University:Natural Science, 2014, 35(3):323-327. )
[10] 于坤杰, 王昕, 王振雷. 基于反馈的精英教学优化算法[J] . 自动化学报, 2014, 40(9):1976-1983. (Yu Kunjie, Wang Xin, Wang Zhenlei. Elitist teaching-learning-based optimization algorithm based on Feedback[J] . Acta Automatica Sinica, 2014, 40(9):1976-1983. )
[11] 拓守恒, 雍龙泉, 邓方安. “教与学”优化算法研究综述[J] . 计算机应用研究, 2013, 30(7):1933-1938. (Tuo Shouheng, Yong Longquan, Deng Fang’an. Survey of teaching-learning-based optimization algorithms[J] . Application Research of Computers, 2013, 30(7):1933-1938. )
[12] Hemmelmayr V C, Doerner K F, Hartl R F. A variable neighborhood search heuristic for periodic routing problems[J] . European Journal of Operational Research, 2009, 195(3):791-802.
[13] Hall N G, Posner M E. Generating experimental data for computational testing with machine scheduling applications[J] . Operations Research, 2001, 49(6):854-865.
[14] AlRashidi M R, El-Hawary M E. A survey of particle swarm optimization applications in electric power systems[J] . IEEE Trans on Evo-lutionary Computation, 2009, 13(4):913-918.
收稿日期 2017/9/26
修回日期 2017/11/2
页码 673-676
中图分类号 TP301.6
文献标志码 A