考虑成本的最大延迟时间同类机调度问题

doi:10.12005/orms.2019.0288

运筹与管理 ›› 2019, Vol. 28 ›› Issue (12): 178-184.DOI: 10.12005/orms.2019.0288

考虑成本的最大延迟时间同类机调度问题

李凯^1,2, 杨阳¹, 刘渤海^1,2

1. 合肥工业大学管理学院,安徽合肥 230009;
2. 过程优化与智能决策教育部重点实验室,安徽合肥 230009

收稿日期:2018-10-24 出版日期:2019-12-25
作者简介:李凯(1977-),男,安徽蒙城人,合肥工业大学教授,研究方向:生产调度,供应链管理、优化算法等;杨阳(1994-),男,安徽合肥人,硕士研究生,研究方向:生产调度。
基金资助:
国家自然科学基金资助项目(71521001,71471052);安徽省自然科学基金资助项目(1708085MG169)

Uniform Parallel Machine Scheduling Problem with Machine Cost to Minimize the Maximal Lateness

LI Kai^1,2, YANG Yang¹, LIU Bo-hai^1,2

1. School of Management, Hefei University of Technology, Hefei 230009, China;
2. Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei 230009, China

Received:2018-10-24 Online:2019-12-25

摘要/Abstract

摘要： 假定生产时机器成本是固定的,研究了一类考虑成本的同类机调度问题,调度的目标是在给定加工完所有作业的总预算的成本限制下最小化最大作业延迟时间。为该类问题构建了混合整数规划模型。通过设计相关规则在机器成本预算内来选择加工机器,以及对传统的LPT(最长加工时间优先)、ECT(最早完工时间优先)、EDD(最早工期优先)等算法进行改进,提出了一个启发式算法H,并理论证明了该算法在同型机和同类机下的最坏误差界。通过算例说明了算法的执行情况,同时也考虑了给定总预算不同的多种情形,采用大量随机数据实验验证了算法的有效性。

关键词: 同类机, 机器成本, 最大延迟时间

Abstract: In this paper, we assume the using cost of machines cost is fixedand study the uniform parallel machine scheduling problem considering the using cost of machines. The goal is to minimize the maximum lateness whose total cost does not exceed a given budget. A mixed integer programming model is established for this problem. To minimize the maximum lateness, we design the rule to select suitable machines in all the machines. Then we propose an improvement of the traditional LPT(Longest Processing Time First)algorithm, ECT(Earliest Completion Time First) algorithm,and EDD(Earliest Due Date First) algorithm. A heuristic algorithm named H is designed. The worst error bounds of the algorithm under parallel machine and uniform parallel machine are also analyzed theoretically. By giving two examples, we illustrate the implementation of the algorithm. Finally, a variety of total cost budgets are considered and the effectiveness of the algorithm is verified by a large number of random data experiments.

Key words: uniform parallel machine, cost of machines, maximal lateness

中图分类号:

O223
TP301

李凯, 杨阳, 刘渤海. 考虑成本的最大延迟时间同类机调度问题[J]. 运筹与管理, 2019, 28(12): 178-184.

LI Kai, YANG Yang, LIU Bo-hai. Uniform Parallel Machine Scheduling Problem with Machine Cost to Minimize the Maximal Lateness[J]. Operations Research and Management Science, 2019, 28(12): 178-184.

参考文献

[1] Zou J, Zhang Y, Miao C. Uniform parallel-machine scheduling with time dependentprocessing times[J]. Journal of the Operations Research Society of China, 2013, 1(2): 239-252.
[2] Kim E S. Scheduling of uniform parallel machines with s-precedenceconstraints[J]. Mathematical & Computer Modelling, 2011, 54(1-2): 576-583.
[3] Lin S W, Ying K C. Uniform parallel-machinescheduling for minimizing totalresource consumption with a bounded makespan[J]. IEEE Access, 2017, (99): 1-1.
[4] Lee W C, Chuang M C, Yeh W C. Uniform parallel-machine scheduling tominimizemakespan with position-based learning curves[J]. Computers & Industrial Engineering, 2012, 63(4): 813-818.
[5] 马英,杨善林,汤大为.带机器准备时间的同类机调度问题的启发式算法[J].系统工程理论与实践,2012,32(9):2022-2030.
[6] 陈荣军,唐国春.同类机的供应链排序[J].系统工程学报,2010,25(1):62-67.
[7] Imreh C, Noga J. Scheduling with machine cost[C]. RANDOM-APPROX’99, Lecture Notes in Computer Science, 1999. 168-176.
[8] Nagy-Gyrgy J, Imreh C. Online scheduling with machine cost and rejection[J]. Discrete Applied Mathematics, 2007, 155(18): 2546-2554.
[9] Imreh C. On-line scheduling with general machine cost functions[J]. Electronic Notes in Discrete Mathematics, 2009, 157(9): 2070-2077.
[10] Cao D, Chen M, Wan G. Parallel machine selection and job scheduling to minimize machine cost and job tardiness[J]. Computers & Operations Research, 2005, 32(8): 1995-2012.
[11] Leung Y T, Lee K, Pinedo M L. Bi-criteria scheduling with machine assignment costs[J]. International Journal of Production Economics, 2012, 139(1): 321-329.
[12] Jiang Y, He Y. Preemptive online algorithms for scheduling with machine cost[J]. Journal of Computer Science & Technology, 2006, 21(6): 984-988.
[13] Ruiz-Torres A J, López F J, Wojciechowski P J, et al. Parallel machine scheduling problems considering regular measures of performance and machine cost[J]. Journal of the Operational Research Society, 2010, 61(5): 849-857.
[14] 侯彬.考虑机器开关的并行机调度研究[J].工业工程与管理,2011,16(2):60-64.
[15] 刘乐,周泓.新工件到达干扰下单机最大延迟时间重调度[J].系统工程学报,2014,29(4):494-506.
[16] Lin B M T, Jeng A A K. Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs[J]. International Journal of Production Economics, 2004, 91(2):121-134.
[17] Li K, Yang S L, Ma H W. A simulated annealing approach to minimize the maximum lateness on uniform parallel machines[J]. Mathematical & Computer Modelling, 2011, 53(5-6): 854-860.
[18] 张玉忠,王忠志,王长钰.分批排序的“转换引理”及其应用[J].系统科学与数学,2002,22(3):328-333.
[19] 唐恒永,赵传立.排序引论[M].科学出版社,2002.46-48.
[20] Li K, Zhang H J, Cheng B Y, Pardalos P M. Uniform parallel machine scheduling problems with fixed machine cost[J]. Optimization Letters, 2018, 12(1): 73-86.

考虑成本的最大延迟时间同类机调度问题

Uniform Parallel Machine Scheduling Problem with Machine Cost to Minimize the Maximal Lateness

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘春来, 王建军. 具有老化效应的单机共同工期安排和工件可拒绝排序问题[J]. 运筹与管理, 2021, 30(7): 66-70.
[2]	王磊, 柏庆国, 任建峰. 具有两种运输方式选择的物流排序问题[J]. 运筹与管理, 2021, 30(6): 1-5.
[3]	姜昆. 带凸资源和恶化效应的单机松弛窗口排序[J]. 运筹与管理, 2020, 29(7): 105-109.
[4]	胡沁, 宁爱兵, 苟海雯, 张惠珍. 精确覆盖问题的加权分治算法[J]. 运筹与管理, 2020, 29(4): 179-186.
[5]	曾守桢, 骆丹丹. 基于投影模型的区间直觉模糊多属性决策方法研究[J]. 运筹与管理, 2020, 29(3): 10-15.
[6]	孙丽, 马卫民. 带恶化和综合学习效应的成组排序问题研究[J]. 运筹与管理, 2020, 29(3): 125-127.
[7]	刘寅斌,胡子怡,李洪波,余咪咪. 可抢占条件下的项目调度研究综述[J]. 运筹与管理, 2019, 28(4): 191-195.
[8]	刘春来, 王建军. 具有学习和退化效应的单机干扰管理问题[J]. 运筹与管理, 2019, 28(1): 94-100.
[9]	郭苗苗, 刘桓, 王吉波, 牛玉萍. 具有学习效应和加工时间可控的平行机排序问题[J]. 运筹与管理, 2018, 27(3): 113-117.
[10]	余英, 程明宝. 带学习效应和资源依赖的单机排序模型[J]. 运筹与管理, 2018, 27(1): 53-58.
[11]	于瑞华, 成央金. 直觉模糊多属性的意见集中排序法[J]. 运筹与管理, 2018, 27(1): 59-62.
[12]	刘乐. 单机单转包商调度与外包联合优化问题的改进启发式算法[J]. 运筹与管理, 2017, 26(11): 49-58.
[13]	闫萍, 王吉波, 赵礼强. 带准备时间的单机指数时间学习效应排序问题[J]. 运筹与管理, 2017, 26(11): 70-76.
[14]	姜永. 多值不确定型直觉模糊识别决策方法[J]. 运筹与管理, 2017, 26(5): 69-73.
[15]	包晓光, 刘朝晖, 余炜. 线形网络上单台车辆分群调度问题[J]. 运筹与管理, 2017, 26(5): 125-129.