2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

带有线性恶化工件和释放时间的两个代理单机调度问题

赵晓丽 唐立新

赵晓丽, 唐立新. 带有线性恶化工件和释放时间的两个代理单机调度问题. 自动化学报, 2015, 41(1): 104-112. doi: 10.16383/j.aas.2015.c140169
引用本文: 赵晓丽, 唐立新. 带有线性恶化工件和释放时间的两个代理单机调度问题. 自动化学报, 2015, 41(1): 104-112. doi: 10.16383/j.aas.2015.c140169
ZHAO Xiao-Li, TANG Li-Xin. Two-agent Scheduling with Linear-deteriorating Jobs and Release Dates on a Single Machine. ACTA AUTOMATICA SINICA, 2015, 41(1): 104-112. doi: 10.16383/j.aas.2015.c140169
Citation: ZHAO Xiao-Li, TANG Li-Xin. Two-agent Scheduling with Linear-deteriorating Jobs and Release Dates on a Single Machine. ACTA AUTOMATICA SINICA, 2015, 41(1): 104-112. doi: 10.16383/j.aas.2015.c140169

带有线性恶化工件和释放时间的两个代理单机调度问题

doi: 10.16383/j.aas.2015.c140169
基金项目: 

国家自然科学基金重点项目(71032004);国家自然科学基金创新研究群体科学基金项目(71321001)资助

详细信息
    作者简介:

    赵晓丽 东北大学工业工程与物流优化研究所,辽宁省制造系统与物流优化重点实验室博士研究生.主要研究方向为生产调度与组合最优化. E-mail:zhaoxiaoli824@163.com

    通讯作者:

    唐立新 东北大学工业工程与物流优化研究所,辽宁省制造系统与物流优化重点实验室教授.主要研究方向为生产调度,物流与供应链管理和组合最优化.本文通信作者. E-mail:lixintang@mail.neu.edu.cn

Two-agent Scheduling with Linear-deteriorating Jobs and Release Dates on a Single Machine

Funds: 

Supported by Supported by Key Project of National Natural Science Foundation of China (71032004), the Fund for Innovative Research Groups of the National Natural Science Foundation of China (71321001)

  • 摘要: 研究了带有简单线性恶化工件和释放时间的两个代理单机调度问题. 所有工件在一台机器上加工, 每个代理有各自依赖于自己工件的优化目标. 针对工件释放时间相同与不同两种情况, 研究了有约束的优化模型, 即找到调度最小化一个代理的目标函数而使得另一个代理的目标函数不超过一个给定的上界. 当工件具有相同的释放时间, 我们主要考虑的目标函数有: 总加权完工时间和总加权拖期工件数. 当工件具有不同释放时间, 我们考虑的目标函数有: 最大完工时间、总完工时间以及拖期工件数. 对于每一个问题, 我们分析了问题的计算复杂性. 此外, 对于NP难问题的一些特殊情况本文分析了最优解性质, 基于这些性质给出了最优算法.
  • [1] Baker K R, Smith J C. A multiple-criterion model for machine scheduling. Journal of Scheduling, 2003, 6(1): 7-16
    [2] Agnetis A, Mirchandani P B, Pacciarelli D, Pacifici A. Scheduling problems with two competing agents. Operations Research, 2004, 52(2): 229-242
    [3] Ng C T, Cheng T C E, Yuan J J. A note on the complexity of the problem of two-agent scheduling on a single machine. Journal of Combinatorial Optimization, 2006, 12(4): 387-394
    [4] Cheng T C E, Ng C T, Yuan J J. Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 2006, 362(1-3): 273-281
    [5] Agnetis A, Pacciarelli D, Pacifici A. Multi-agent single machine scheduling. Annals of Operations Research, 2007, 150(1): 3-15
    [6] Cheng T C E, Ng C T, Yuan J J. Multi-agent scheduling on a single machine with max-form criteria. European Journal of Operational Research, 2008, 188(2): 603-609
    [7] Lee K B, Choi B C, Leung J Y T, Pinedo M L. Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Information Processing Letters, 2009, 109(16): 913-917
    [8] Leung J Y T, Pinedo M L, Wan G. Competitive two agent scheduling and its applications. Operations Research, 2010, 58(2): 458-469
    [9] Wan G H, Vakati S R, Leung J Y T, Pinedo M. Scheduling two agents with controllable processing times. European Journal of Operational Research, 2010, 205(3): 528-539
    [10] Mor B, Mosheiov G. Scheduling problems with two competing agents to minimize minmax and minsum earliness measures. European Journal of Operational Research, 2010, 206(3): 540-546
    [11] Mor B, Mosheiov G. Single machine batch scheduling with two competing agents to minimize total flowtime. European Journal of Operational Research, 2011, 215(3): 524-531
    [12] Li S S, Yuan J J. Unbounded parallel-batching scheduling with two competitive agents. Journal of Scheduling, 2012, 15(5): 629-640
    [13] Fan B Q, Cheng T C E, Li S S, Feng Q. Bounded parallel-batching scheduling with two competing agents. Journal of Scheduling, 2013, 16(3): 261-271
    [14] Cheng T C E, Ding Q, Lin B M T. A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 2004, 152(1): 1-13
    [15] Mosheiov G. Scheduling jobs under simple linear deterioration. Computers and Operations Research, 1994, 21(6): 653-659
    [16] Ng C T, Li S S, Cheng T C E, Yuan J J. Preemptive scheduling with simple linear deterioration on a single machine. Theoretical Computer Science, 2010, 411(40-42): 3578-3586
    [17] Liu P, Tang L X. Two-agent scheduling with linear deteriorating jobs on a single machine. Lecture Notes in Computer Science, 2008, 5092: 642-650
    [18] Liu P, Tang L X, Zhou X Y. Two-agent group scheduling with deteriorating jobs on a single machine. The International Journal of Advanced Manufacturing Technology, 2010, 47(5-8): 657-664
    [19] Liu P, Yi N, Zhou X Y. Two-agent single-machine scheduling problems under increasing linear deterioration. Applied Mathematical Modelling, 2011, 35(5): 2290-2296
    [20] Liu Peng, Zhou Xiao-Ye, Rong Nan. Two-agent scheduling with a learning effect and deteriorating jobs. Journal of Systems Engineering, 2012, 27(6): 841-846 (刘鹏, 周晓晔, 荣楠. 带有学习效应和恶化工件的双代理调度问题. 系统工程学报, 2012, 27(6): 841-846)
    [21] Yin Y Q, Cheng S R, Wu C C. Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Information Sciences, 2012, 189: 282-292
    [22] Yin Y Q, Wu W H, Cheng S R, Wu C C. An investigation on a two-agent single-machine scheduling problem with unequal release dates. Computers and Operations Research, 2012, 39(12): 3062-3073
    [23] Lee W C, Chung Y H, Hu M C. Genetic algorithms for a two-agent single-machine problem with release time. Applied Soft Computing, 2012, 12(11): 3580-3589
    [24] Wu C C, Wu W H, Chen J C, Yin Y Q, Wu W H. A study of the single-machine two-agent scheduling problem with release times. Applied Soft Computing, 2013, 13(2): 998-1006
    [25] Cheng T C E, Chung Y H, Liao S C, Lee W C. Two-agent single-machine scheduling with release times to minimize the total weighted completion time. Computers and Operations Research, 2013, 40(1): 353-361
    [26] Li D C, Hsu P H. Competitive two-agent scheduling with learning effect and release times on a single machine. Mathematical Problems in Engineering, 2013, 2013, Article ID 754826, doi: 10.1155/2013/754826
    [27] Kung J Y, Chao Y P, Lee K I, Kang C C, Lin W C. Two-agent single-machine scheduling of jobs with time-dependent processing times and ready times. Mathematical Problems in Engineering, 2013, 2013, Article ID 806325, DOI: 10.1155/2013/806325
    [28] Johnson D S. The NP-complete columns: an ongoing guide. Journal of Algorithms, 1981, 2(4): 393-405
    [29] Ji M, He Y, Cheng T C E. Scheduling linear deteriorating jobs with an availability constraint on a single machine. Theoretical Computer Science, 2006, 362(1-3): 115-126
    [30] Kononov A. Combinatorial complexity of scheduling jobs with simple linear processing times. Diskretny Analiz i Issledovanie Operatsii, 1996, 3(2): 15-32 (in Russian)
  • 加载中
计量
  • 文章访问数:  1922
  • HTML全文浏览量:  105
  • PDF下载量:  669
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-03-20
  • 修回日期:  2014-07-31
  • 刊出日期:  2015-01-20

目录

    /

    返回文章
    返回