分支定界算法求解带有释放时间的单机双代理调度问题

doi:10.12005/orms.2019.0227

运筹与管理 ›› 2019, Vol. 28 ›› Issue (10): 83-88.DOI: 10.12005/orms.2019.0227

分支定界算法求解带有释放时间的单机双代理调度问题

梁建恒¹, 薛含钰¹, 白丹宇², 苗蕴慧¹

1. 沈阳化工大学经济与管理学院,辽宁沈阳 110142;
2. 大连海事大学航运经济与管理学院,辽宁大连 116026

收稿日期:2017-11-22 出版日期:2019-10-25
通讯作者: 白丹宇^*(1978-),男,辽宁省沈阳市,博士,教授、硕士生导师,管理科学与工程
作者简介:梁建恒(1991-),女,内蒙古太仆寺旗,研究生,物流与供应链管理;薛含钰(1993-),女,吉林省吉林市,研究生,物流与供应链管理;苗蕴慧(1983-),女,辽宁省抚顺市,博士,讲师、硕士生导师,行为运作管理。
基金资助:
国家自然科学基金资助项目(61873173,71601127)

A Branch and Bound Algorithm for the Bi-agent Single-machine Scheduling Problem with Release Dates

LIANG Jian-heng¹, XUE Han-yu¹, BAI Dan-yu^2*, MIAO Yun-hui¹

1. School of Economics & Management, Shenyang University of Chemical Technology, Shenyang 110142, China;
2. School of Maritime Economics & Management, Dalian Maritime University,Dalian116026, China

Received:2017-11-22 Online:2019-10-25

摘要/Abstract

摘要： 本文研究了带有释放时间的单机双代理调度问题,目标函数为极小化最大完工时间和。为了便于利用优化软件求解,建立了混合整数规划模型。考虑到该问题具有NP困难性,因此采用近似与精确算法分别求解不同规模问题。针对大规模问题,提出了优势代理优先启发式算法,并证明了其渐近最优性。针对小规模问题,设计了分支定界法进行最优求解,其中基于释放时间的分支规则和基于加工中断的下界有效地减少了运算时间。最后,通过数值测试验证了分支定界算法的有效性以及启发式算法的收敛性。

关键词: 调度, 单机, 双代理, 分支定界

Abstract: This paper investigates a bi-agent single-machine scheduling problem with release dates. The objective is to minimize the sum of makespans. A mixed integer programming model is established for solving the problem by using optimization software. Given the NP-hardness of the problem, approximate and accurate algorithms are presented to handle different scale instances. For large-scale problems, available dominance agent first heuristic algorithm is proposed and its asymptotic optimality is proved. For small-scale problems, a branch and bound algorithm is designed to obtain optimal solution, in which a release-date-based branching rule and a preemption-based lower bound reduce the running time effectively. Numerical experiments show the effectiveness of the proposed algorithms.

Key words: scheduling, single-machine, bi-agent, branch and bound

中图分类号:

梁建恒, 薛含钰, 白丹宇, 苗蕴慧. 分支定界算法求解带有释放时间的单机双代理调度问题[J]. 运筹与管理, 2019, 28(10): 83-88.

LIANG Jian-heng, XUE Han-yu, BAI Dan-yu, MIAO Yun-hui. A Branch and Bound Algorithm for the Bi-agent Single-machine Scheduling Problem with Release Dates[J]. Operations Research and Management Science, 2019, 28(10): 83-88.

参考文献

[1] Graham R L, Lawler E L, Lenstra J K,Kan A H G R. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5(1): 287-326.
[2] Agnetis A, Mirchandani P B, Pacciarelli D, Pacifici A. Scheduling problems with two competing agents[J]. Operations Research, 2004, 52(2): 229-242.
[3] Agnetis A, Billaut J C, Gawiejnowicz S, Pacciarelli D, Soukhal A. Multiagent scheduling: models and algorithms[M]. Springer Berlin, 2014.
[4] Chenga T C E, Nga C T, Yuanb J J. Multi-agent scheduling on a single machine with max-form criteria[J]. European Journal of Operational Research, 2008, 188(2): 603-609.
[5] Yin Y, Cheng S R, Cheng T C E, Wu C C, Wu W H. Two-agent single-machine scheduling with assignable due dates[J]. Applied Mathematics & Computation, 2012, 219(4): 1674-1685.
[6] Lee W C, Chung Y H, Hu M C. Genetic algorithms for a two-agent single-machine problem with release time[J]. Applied Soft Computing, 2012,12(11): 3580-3589.
[7] Cheng T C E, Chung Y H, Liao S C, Lee W C. Two-agent singe-machine scheduling with release times to minimize the total weighted completion time[J]. Computers & Operations Research, 2013, 40(1): 353-361.
[8] Wu C C, Huang S K, Lee W C. Two-agent scheduling with learning consideration[J]. Computer&Industrial Engineering, 2011, 61(4): 1324-1335.
[9] Cheng T C E, Cheng S R, Wu W H, Hsu P H, Wu C C. A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learningconsiderations[J]. Computers & Industrial Engineering, 2011, 60(4): 534-541.
[10] Liu P, Yi N, Zhou X, Gong H. Scheduling two agents with sum-of-processing-times-based deterioration on a single machine[J]. Applied Mathematics & Computation, 2013, 219(17): 8848-8855.
[11] Wu W H, Xu J, Wu W H, Yin Y, Cheng I F, Wu C C. A tabu method for a two-agent single-machine scheduling with deterioration jobs[J]. Computers & Operations Research, 2013, 40(8): 2116-2127.
[12] Ding G, Sun S. Single-machine scheduling problems with two agents competing for makespan[J]. Lecture Notes in Computer Science, 2010, 6328: 244-255.
[13] Kaminsky P, Simchi-Levi D. Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates[J]. Operations Research Letters, 2001, 29: 141-148.

[1]	郑红星, 段爽, 孙丛. 考虑翻箱的场桥调度和提箱集卡数量的集成优化[J]. 运筹与管理, 2021, 30(9): 48-55.
[2]	马咏, 何正文, 江波, 王能民. 一种求解柔性资源约束前摄性项目调度问题的启发式算法[J]. 运筹与管理, 2021, 30(8): 14-20.
[3]	庞南生, 叶博童. 项目鲁棒调度的资源分配启发式算法研究[J]. 运筹与管理, 2021, 30(8): 21-27.
[4]	陈可嘉, 段瑞明, 刘碧玉, 周晓敏. 模糊置换流水车间调度的多目标模型[J]. 运筹与管理, 2021, 30(8): 28-36.
[5]	刘万琳, 张静文, 刘婉君. 带有资源柔性约束的max-NPV分布式多项目调度问题[J]. 运筹与管理, 2021, 30(8): 37-43.
[6]	陈伟, 张玉林. “仓店一体化”模式下订单拣选与配送集成调度优化[J]. 运筹与管理, 2021, 30(7): 16-22.
[7]	刘春来, 王建军. 具有老化效应的单机共同工期安排和工件可拒绝排序问题[J]. 运筹与管理, 2021, 30(7): 66-70.
[8]	范厚明, 孔靓, 岳丽君. 考虑出口箱进出场及预翻箱的箱位分配与场桥调度协同优化[J]. 运筹与管理, 2021, 30(6): 26-34.
[9]	黄辉, 梁星, 李梦想, 张娟. 应急物资联合配送决策研究[J]. 运筹与管理, 2021, 30(6): 48-54.
[10]	董君, 叶春明. 具有学习效应的半导体晶圆制造绿色车间调度问题研究[J]. 运筹与管理, 2021, 30(4): 217-223.
[11]	张静文, 刘婉君, 李琦. 基于关键链改进搜索的遗传算法求解分布式多项目调度[J]. 运筹与管理, 2021, 30(3): 123-129.
[12]	宁敏静, 郑小强, 何正文. 基于随机活动工期的现金流动态均衡前摄性与反应性项目调度优化[J]. 运筹与管理, 2021, 30(2): 117-123.
[13]	郑斐峰, 宋沁睿, 徐寅峰, 刘明. 考虑加工速率相互干扰的平行机调度最优策略研究[J]. 运筹与管理, 2021, 30(12): 1-5.
[14]	刘国山, 王敏, 张转霞. 基于时间窗延迟的资源约束项目调度双层优化研究[J]. 运筹与管理, 2021, 30(12): 6-12.
[15]	王艳婷, 何正文, 和媛媛. 随机环境下基于成本经济的项目调度权衡优化研究[J]. 运筹与管理, 2021, 30(12): 20-27.

分支定界算法求解带有释放时间的单机双代理调度问题

A Branch and Bound Algorithm for the Bi-agent Single-machine Scheduling Problem with Release Dates

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics