The Competing Job Sets Scheduling Problems With Two Types of Release Dates on Batching-Machine
-
摘要: 研究了两个工件集合竞争在一台批处理机上加工的调度问题, 其中每个集合的工件具有一个共同的释放时间.批处理机可以同时加工多个工件作为一批, 每批的加工时间为该批工件中加工时间的最大值.基于两类释放时间的大小, 针对无界批处理机上最小化一个集合工件的最大完工时间、最大延迟以及总完工时间, 使得另一个集合工件的最大完工时间不超过给定上界问题, 分别给出了最优求解方法.针对有界批处理机上最小化一个集合工件的最大完工时间, 使得另一个集合工件的最大完工时间不超过给定上界问题, 证明为一般意义NP--!难问题, 并给出伪多项式时间最优求解方法.Abstract: We consider two sets of jobs competing a single parallel-batching machine where the jobs of each set have a common release date. The parallel-batching machine can process several jobs simultaneously as a batch, and the processing time of a batch is the largest of the job processing times in the batch. Based on the sizes of the two types of release dates, the optimal solutions are presented on minimizing the makespan, the maximum lateness and the total completion time of one set of jobs, respectively, such that the makespan of the other set of jobs is maintained under a fixed value on an unbounded batching machine. For the bounded batching machine, minimizing the makespan of one set of jobs subject to an upper bound on the makespan of the other set of jobs is proved to be ordinary m NP-hard, and pseudo-polynomial time optimal solutions are given.
-
Key words:
- Scheduling /
- competing job sets /
- release date /
- batching machine
1) 本文责任编委 乔俊飞 -
[1] Baker K R, Smith J C. A multiple-criterion model for machine scheduling. Journal of Scheduling, 2003, 6(1): 7-16 doi: 10.1023/A:1022231419049 [2] Agnetis A, Mirchandani P B, Pacciarelli D, Pacifici A. Scheduling problems with two competing agents. Operations Research, 2004, 52(2): 229-242 doi: 10.1287/opre.1030.0092 [3] Perez-Gonzalez P, Framinan J M. A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: multi-agent scheduling problems. European Journal of Operational Research, 2014, 235(1): 1-16 http://cn.bing.com/academic/profile?id=d83ba5b1366d427e307f2996e67e39a1&encoded=0&v=paper_preview&mkt=zh-cn [4] Agnetis A, Billaut J C, Gawiejnowicz S, Pacciarelli D, Soukhal A. Multiagent Scheduling: Models and Algorithms. Heidelberg: Springer, 2014. [5] Li S S, Yuan J J. Unbounded parallel-batching scheduling with two competitive agents. Journal of Scheduling, 2012, 15(5): 629-640 doi: 10.1007/s10951-011-0253-x [6] 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 doi: 10.1007/s10951-012-0274-0 [7] Wang J Q, Fan G Q, Zhang Y Q, Zhang C W, Leung J Y T. Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes. European Journal of Operational Research, 2017, 258(2): 478-490 doi: 10.1016/j.ejor.2016.10.024 [8] Tang L X, Zhao X L, Liu J Y, Leung J Y T. Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine. European Journal of Operational Research, 2017, 263(2): 401-411 doi: 10.1016/j.ejor.2017.05.019 [9] 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 & Operations Research, 2012, 39(12): 3062-3073 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=a9a59b2f6984e4385a5c3da81206fd84 [10] 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 doi: 10.1016/j.asoc.2012.06.015 [11] 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 doi: 10.1016/j.asoc.2012.10.003 [12] 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. Computers & Operations Research, 2013, 40(1): 353-361 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=30b2aab966d975e2914462ee77a86bc1 [13] Dover O, Shabtay D. Single machine scheduling with two competing agents, arbitrary release dates and unit processing times. Annals of Operations Research, 2016, 238(1-2): 145-178 doi: 10.1007/s10479-015-2054-7 [14] Potts C N, Kovalyov M Y. Scheduling with batching: a review. European Journal of Operational Research, 2000, 120(2): 228-249 doi: 10.1016/S0377-2217(99)00153-8 [15] Brucker P, Gladky A, Hoogeveen H, Kovalyov M Y, Potts C N, Tautenhahn T, et al. Scheduling a batching machine. Journal of Scheduling, 1998, 1(1): 31-54 doi: 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R [16] Lee C Y. Minimizing makespan on a single batch processing machine with dynamic job arrivals. International Journal of Production Research, 1999, 37(1): 219-236 doi: 10.1080/002075499192020 [17] Liu Z H, Yu W C. Scheduling one batch processor subject to job release dates. Discrete Applied Mathematics, 2000, 105(1-3): 129-136 doi: 10.1016/S0166-218X(00)00181-5 [18] Liu Z H, Cheng T C E. Approximation schemes for minimizing total (weighted) completion time with release dates on a batch machine. Theoretical Computer Science, 2005, 347(1-2): 288-298 doi: 10.1016/j.tcs.2005.07.028 -
下载:
图(3)
计量
- 文章访问数: 1580
- HTML全文浏览量: 298
- PDF下载量: 113
- 被引次数: 0
