关于带运输的单机调度在线问题的研究

doi:10.15960/j.cnki.issn.1007-6093.2022.01.009

Abstract

Abstract:

This paper studies the single machine online scheduling problem with transporters. The problem assumes that the jobs arrive online over time, and there is only a single transporter in the system, which transports up to $k$ jobs each time. Each job needs to be processed on a single machine, and then transported to the destination by the transporter. The objective of the problem is to minimize the makespan, that is, the shortest time for all jobs to be processed and transported to the destination. For this problem, this paper studies the agreeable model, and proposes an online algorithm with the competitive ratio of $\frac{\sqrt{5}+1}{2}$ based on the greedy strategy, in the end, the algorithm is proved to be the optimal online algorithm.

Key words: transporter, single machine scheduling, online algorithm

CLC Number:

O157

Yinling WANG, Xin HAN, Xinxin SHAO. Online single machine scheduling problem with transportation[J]. Operations Research Transactions, 2022, 26(1): 125-133.

References 35

1	Potts C N . Analysis of a Heuristic for one machine sequencing with release dates and delivery times[J]. Operations Research, 1980, 28 (6): 1436- 1441. doi: 10.1287/opre.28.6.1436
2	Hall L A , Shmoys D B . Jackson's rule for one-machine scheduling: making a good heuristic better[J]. Mathematics of Operations Research, 1992, 17 (1): 22- 35. doi: 10.1287/moor.17.1.22
3	Woeginger G J . Heuristics for parallel machine scheduling with delivery times[J]. ACTA Informatica, 1994, 31 (6): 503- 512. doi: 10.1007/BF01213203
4	Chen Z . Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs[J]. European Journal of Operational Research, 1996, 93 (1): 49- 60. doi: 10.1016/0377-2217(95)00133-6
5	Cheng T , Gordon V S , Kovalyov M Y . Single machine scheduling with batch deliveries[J]. European Journal of Operational Research, 1996, 94 (2): 277- 283. doi: 10.1016/0377-2217(96)00127-0
6	Herrmann J W , Lee C Y . On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date[J]. European Journal of Operational Research, 1993, 70 (3): 272- 288. doi: 10.1016/0377-2217(93)90239-J
7	Yuan J . A note on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs[J]. European Journal of Operational Research, 1996, 94 (1): 203- 205. doi: 10.1016/0377-2217(95)00168-9
8	Lee C Y , Chen Z . Machine scheduling with transportation considerations[J]. Journal of Scheduling, 2001, 4 (1): 3- 24. doi: 10.1002/1099-1425(200101/02)4:1<3::AID-JOS57>3.0.CO;2-D
9	Chang Y C , Lee C Y . Machine scheduling with job delivery coordination[J]. European Journal of Operational Research, 2004, 158 (2): 470- 487. doi: 10.1016/S0377-2217(03)00364-3
10	Lu L , Yuan J . Single machine scheduling with job delivery to minimize makespan[J]. Asia Pacific Journal of Operational Research, 2008, 25 (1): 1- 10. doi: 10.1142/S0217595908001596
11	Li G , Lu X . Approximation algorithms for the single-machine scheduling with a period of maintenance[J]. Optimization Letters, 2016, 10 (3): 543- 562. doi: 10.1007/s11590-015-0881-8
12	Hoogeveen J A , Vestjens A . Optimal on-line algorithms for single-machine scheduling[J]. Lecture Notes in Computer Science, 1999, 1084, 404- 414.
13	Anderson E J , Potts C N . Online scheduling of a single machine to minimize total weighted completion time[J]. Mathmatics of Operations Research, 2004, 29, 686- 697. doi: 10.1287/moor.1040.0092
14	Deng X , Poon C K , Zhang Y . Approximation Algorithms in Batch Processing[M]. Berlin: Springer, 2003.
15	Hoogeveen J A , Vestjens A . A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine[J]. SIAM Journal on Discrete Mathematics, 2000, 13 (1): 56- 63. doi: 10.1137/S0895480196296823
16	Zhang G , Cai X , Wong C K . Online algorithms for minimizing makespan on batch processing machines[J]. Naval Research Logistics, 2010, 48 (3): 241- 258.
17	Lee C Y , Uzsoy R . Minimizing makespan on a single batch processing machine with dynamic job arrivals[J]. International Journal of Production Research, 1999, 37 (1): 219- 236. doi: 10.1080/002075499192020
18	Liu Z , Yu W . Scheduling one batch processor subject to job release dates[J]. Discrete Applied Mathematics, 2000, 103 (1-3): 129- 136.
19	Liu H , Yuan J , W Li . Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart[J]. Journal of Combinatorial Optimization, 2016, 31 (4): 1609- 1622. doi: 10.1007/s10878-015-9844-3
20	Lu L , Zhang L . Competitive project scheduling on two unbounded parallel batch machines[J]. Journal of the Operations Research Society of China, 2017, 6 (3): 473- 483.
21	李文杰, 马冉. 最大化接收工件个数的在线分批排序问题研究[J]. 郑州大学学报(理学版), 2016, 2016 (2): 24- 28.
22	Lucier B, Menache I, Naor J, et al. Efficient online scheduling for deadline-sensitive jobs: extended abstract[C]//Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013: 305-314.
23	Azar Y, Kalp S I, Lucier B, et al. Truthful online scheduling with commitments[C]//Proceedings of the ACM Symposium on Economics and Computations (EC), 2015: 715-732.
24	Bansal N, Chan H L, Pruhs K. Competitive algorithms for due date scheduling[C]//Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2007: 28-39.
25	Baruah S K , Haritsa J R . Scheduling for over load in real time systems[J]. IEEE Transactions on Computers, 1997, 46 (9): 1034- 1039. doi: 10.1109/12.620484
26	Baruah S K, Haritsa J R, Sharma N. On-line scheduling to maximize task completions[C]//Proceedings of the IEEE Real-Time Systems Symposium (RTSS), 1994: 228-236.
27	Garay J A, Naor J, Yener B, Zhao P. On-line admission control and packet scheduling with interleaving[C]//Proceedings of the IEEE International Conference on Computer Communi cations (INFOCOM), 2002: 94-103.
28	Georgiadis L , Guerin R , Parekh A K . Optimal multiplexing on a single link: delay and buffer requirements[J]. IEEE Transactions on Information Theory, 1997, 43 (5): 1518- 1535. doi: 10.1109/18.623149
29	Goldwasser M H. Patience is a virtue: the effect of slack on competitiveness for admission control[C]//Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999: 396-405.
30	Im S, Moseley B. General profit scheduling and the power of migration on heterogeneous ma chines[C]//Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016: 165-173.
31	Liebeherr J , Wrege D E , Fer-rari D . Exact admission control for networks with a bounded delay service[J]. IEEE/ACM Transactions on Networking, 1996, 4 (6): 885- 901. doi: 10.1109/90.556345
32	Lucier B, Menache I, Naor J, et al. Efficient online scheduling for deadline-sensitive jobs: extended abstract[C]//Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013: 305-314.
33	Pruhs K, Stein C. How to schedule when you have to buy your energy[C]//Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2010: 352-365.
34	Schwiegelshohn C, Schwiegelshohn U. The power of migration for online slack scheduling[C]//Proceedings of the European Symposium of Algorithms (ESA), 2016: 1-17.
35	Chen L , Eberle F , Megow N . A general framework for handling commitment in online through put maximization[J]. Mathematical Programming, 2020, 183 (9): 215- 247.

[1]	WANG Libo, LI Wenhua, YU Dan. Online scheduling on single batch machine with variable lookahead interval [J]. Operations Research Transactions, 2022, 26(1): 134-140.
[2]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[3]	PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times [J]. Operations Research Transactions, 2019, 23(1): 111-118.
[4]	LI Ying, QIAO Longliang, ZHENG Feifeng. A study of online berth and quay crane integrated allocation problem with lookahead ability [J]. Operations Research Transactions, 2018, 22(3): 28-36.
[5]	WANG Chengfei, ZHANG Yuzhong. Online batch scheduling with known information in advance [J]. Operations Research Transactions, 2016, 20(1): 84-90.
[6]	WANG Cheng-Fei, ZHANG Yu-Zhong, MIAO Cui-Xia, BAI Qing-Guo. Online Batch Scheduling with Linear Deterioration Effect [J]. Operations Research Transactions, 2011, 15(3): 107-114.

Online single machine scheduling problem with transportation

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 35

Related Articles 6

Recommended Articles

Metrics

Comments