English

运筹学学报 >

2022 , Vol. 26 >Issue 1: 125 - 133

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.01.009

 

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

展开
  • 1. 大连理工大学数学科学学院, 辽宁大连, 116024
    2. 大连理工大学软件学院, 辽宁大连, 116024
    3. 大连东软信息学院软件学院, 辽宁大连, 116023
王银铃    E-mail: yinling_wang@foxmail.com

收稿日期: 2021-06-04

  网络出版日期: 2022-03-14

基金资助

国家自然科学基金青年基金(11701062)

收起

Online single machine scheduling problem with transportation

Expand
  • 1. School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, Liaoning, China
    2. School of Software Technology, Dalian University of Technology, Dalian 116024, Liaoning, China
    3. School of Software, Dalian Neusoft University of Information, Dalian 116023, Liaoning, China

Received date: 2021-06-04

  Online published: 2022-03-14

Fold

摘要

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达，系统中有一台运输机，该运输机每次最多运输$k$个工件，每个工件需要先在单机上完成加工，然后再被运输机运往目的地，问题的优化目标为最小化完工时间，即所有工件被加工完并且运往目的地的时间最短。针对该问题，作者研究了工件满足一致性条件的模型，并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法，并且证明该算法是最优在线算法。

关键词： 运输机; 单机调度; 在线算法

本文引用格式

王银玲, 韩鑫, 邵欣欣 . 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022 , 26(1) : 125 -133 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.009

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

参考文献

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.
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.
3 Woeginger G J . Heuristics for parallel machine scheduling with delivery times[J]. ACTA Informatica, 1994, 31 (6): 503- 512.
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.
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.
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.
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.
8 Lee C Y , Chen Z . Machine scheduling with transportation considerations[J]. Journal of Scheduling, 2001, 4 (1): 3- 24.
9 Chang Y C , Lee C Y . Machine scheduling with job delivery coordination[J]. European Journal of Operational Research, 2004, 158 (2): 470- 487.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Options
文章导航

/

〈 〉