Two-agent Scheduling with Linear-deteriorating Jobs and Release Dates on a Single Machine
-
摘要: 研究了带有简单线性恶化工件和释放时间的两个代理单机调度问题. 所有工件在一台机器上加工, 每个代理有各自依赖于自己工件的优化目标. 针对工件释放时间相同与不同两种情况, 研究了有约束的优化模型, 即找到调度最小化一个代理的目标函数而使得另一个代理的目标函数不超过一个给定的上界. 当工件具有相同的释放时间, 我们主要考虑的目标函数有: 总加权完工时间和总加权拖期工件数. 当工件具有不同释放时间, 我们考虑的目标函数有: 最大完工时间、总完工时间以及拖期工件数. 对于每一个问题, 我们分析了问题的计算复杂性. 此外, 对于NP难问题的一些特殊情况本文分析了最优解性质, 基于这些性质给出了最优算法.Abstract: In this paper, we investigate the two-agent single-machine scheduling problem with simple linear-deteriorating jobs and release dates. All the jobs are processed on a common machine, and each agent has respective criterion depending on its own jobs to optimize. In view of identical or different job release dates, the constrained optimization model is studied, which is to schedule the jobs such that the objective of one agent is minimized while the objective of the other agent is less than a given upper bound. For the jobs with identical release dates, the objectives we consider in this paper are total weighted completion times and total weighted number of tardy jobs. For the jobs with distinct release dates, the objectives we consider are makespan, total completion times, and number of tardy jobs. For each problem, we analyze the computational complexity. Moreover, for several special cases of NP-hard problems, we present optimal properties and provide optimal algorithms on the basis of these properties.
-
Key words:
- Scheduling /
- two-agent /
- deteriorating jobs /
- release date /
- single machine
-
[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)
点击查看大图
计量
- 文章访问数: 1778
- HTML全文浏览量: 100
- PDF下载量: 664
- 被引次数: 0