全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

DOI: 10.16383/j.aas.2015.c140169, PP. 104-112

Keywords: 调度,两个代理,恶化工件,释放时间,单机

Full-Text   Cite this paper   Add to My Lib

Abstract:

?研究了带有简单线性恶化工件和释放时间的两个代理单机调度问题.所有工件在一台机器上加工,每个代理有各自依赖于自己工件的优化目标.针对工件释放时间相同与不同两种情况,研究了有约束的优化模型,即找到调度最小化一个代理的目标函数而使得另一个代理的目标函数不超过一个给定的上界.当工件具有相同的释放时间,我们主要考虑的目标函数有:总加权完工时间和总加权拖期工件数.当工件具有不同释放时间,我们考虑的目标函数有:最大完工时间、总完工时间以及拖期工件数.对于每一个问题,我们分析了问题的计算复杂性.此外,对于NP难问题的一些特殊情况本文分析了最优解性质,基于这些性质给出了最优算法.

References

[1]  Li S S, Yuan J J. Unbounded parallel-batching scheduling with two competitive agents. Journal of Scheduling, 2012, 15(5): 629-640
[2]  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
[3]  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
[4]  Mosheiov G. Scheduling jobs under simple linear deterioration. Computers and Operations Research, 1994, 21(6): 653-659
[5]  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
[6]  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
[7]  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
[8]  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
[9]  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)
[10]  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
[11]  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
[12]  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
[13]  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
[14]  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
[15]  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
[16]  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
[17]  Johnson D S. The NP-complete columns: an ongoing guide. Journal of Algorithms, 1981, 2(4): 393-405
[18]  Baker K R, Smith J C. A multiple-criterion model for machine scheduling. Journal of Scheduling, 2003, 6(1): 7-16
[19]  Agnetis A, Mirchandani P B, Pacciarelli D, Pacifici A. Scheduling problems with two competing agents. Operations Research, 2004, 52(2): 229-242
[20]  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
[21]  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
[22]  Agnetis A, Pacciarelli D, Pacifici A. Multi-agent single machine scheduling. Annals of Operations Research, 2007, 150(1): 3-15
[23]  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
[24]  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
[25]  Leung J Y T, Pinedo M L, Wan G. Competitive two agent scheduling and its applications. Operations Research, 2010, 58(2): 458-469
[26]  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
[27]  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
[28]  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
[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)

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133