加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究

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

Abstract

Abstract:

This paper studies the single-machine online schedule under the NDP-constraint to minimize the maximum delivery completion time. Here "NDP-constraint" means that the idle machine must schedule the available jobs at any time, i.e., the available jobs cannot be delayed for processing. In this paper, we study the restricted version in which the jobs have agreeable processing times and delivery times (if $p_{i}\geq p_{j}$, then $p_{i}\geq p_{j}$). we first present a lower bound of 4/3 and then design an online algorithm with the competitive ratio of 1.382.

Key words: online scheduling, online algorithm, NDP-constraint, agreeable, delivery completion time

CLC Number:

O221.7

Wenjie LI, Zhihui DU, Menglong SU. Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times[J]. Operations Research Transactions, 2024, 28(4): 18-28.

References 15

1	唐国春, 张峰, 罗守成, 等. 现代排序论[M]. 上海: 上海科学普及出版社, 2003.
2	万国华. 排序与调度的理论、模型和算法[M]. 北京: 清华大学出版社, 2019.
3	Blazewicz J , Ecker K , Pesch E , et al. Handbook on Scheduling-From Theory to Practice[M]. Switzerland: Springer Nature, 2019.
4	Yuan J J , Ng C T , Cheng T C E . Scheduling with release dates and preemption to minimize multiple max-form objective functions[J]. European Journal of Operational Research, 2020, 280, 860- 875. doi: 10.1016/j.ejor.2019.07.072
5	Baker K R . Introduction to Sequencing and Scheduling[M]. New York: John Wiley & Sons, 1974.
6	Hoogeveen H , Potts C N , Woeginger G J . Online scheduling on a single machine: Maximizing the number of early jobs[J]. Operations Research Letters, 2000, 27, 193- 196. doi: 10.1016/S0167-6377(00)00061-4
7	Keskinocak P. Online algorithms with lookahead: A survey [Z]. ISYE working paper, 1999.
8	Ma R , Guo S N , Miao C X . A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection[J]. Applied Mathematics and Computation, 2021, 392, 125670. doi: 10.1016/j.amc.2020.125670
9	Li W J , Yuan J J . Single-machine online scheduling of jobs with non-delayed processing constraint[J]. Journal of Combinatorial Optimization, 2021, 41, 830- 843. doi: 10.1007/s10878-021-00722-4
10	Graham R L , Lawer E L , Lenstra J K . Optimization and approximation in deterministic sequencing and scheduling[J]. Annals of Discrete Mathematics, 1979, 5, 287- 326.
11	胡觉亮, 张玮虹, 蒋义伟. 生产和运输时间具有一致性的单机在线最优算法[J]. 浙江理工大学学报, 2010, 27, 830- 834.
12	Liu H L , Lu X W , Li W J . A best possible online algorithm for parallel batch scheduling with delivery times and limited restart[J]. Optimization Letters, 2021, 15, 1155- 1173. doi: 10.1007/s11590-020-01618-8
13	Hoogeveen H , Vestjens A P 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, 56- 63. doi: 10.1137/S0895480196296823
14	Tian J , Fu R Y , Yuan J J . A best on-line algorithm for single machine scheduling with small delivery times[J]. Theoretical Computer Science, 2008, 393, 287- 293. doi: 10.1016/j.tcs.2007.11.006
15	Liu M , Chu C B , Xu Y F , et al. An optimal online algorithm for single machine scheduling with bounded delivery times[J]. European Journal of Operational Research, 2010, 201, 693- 700. doi: 10.1016/j.ejor.2009.03.028

[1]	JIAO Chengwen. Online scheduling on a single parallel-batch machine with linear lookahead [J]. Operations Research Transactions, 2024, 28(4): 111-116.
[2]	Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG. Single-machine online scheduling to minimize maximum weighted completion time with limited weights [J]. Operations Research Transactions, 2024, 28(2): 71-80.
[3]	Yubo DAI, Yihong DUAN, Longcheng LIU, Zihao WANG. Randomized approximation algorithms for a class of one-dimensional online unit clustering problem [J]. Operations Research Transactions, 2022, 26(3): 143-150.
[4]	Wenjie LI, Yujing LI, Hailing LIU. Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable [J]. Operations Research Transactions, 2022, 26(2): 55-63.
[5]	Libo WANG, Wenhua LI, Dan YU. Online scheduling on single batch machine with variable lookahead interval [J]. Operations Research Transactions, 2022, 26(1): 134-140.
[6]	Yinling WANG, Xin HAN, Xinxin SHAO. Online single machine scheduling problem with transportation [J]. Operations Research Transactions, 2022, 26(1): 125-133.
[7]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[8]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[9]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[10]	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.
[11]	MIN Xiao, ZHU Junlei, LIU Jing. An online algorithm for hierarchical scheduling on two identical machines with rejection [J]. Operations Research Transactions, 2018, 22(3): 117-124.
[12]	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.
[13]	HOU Liying. Online hierarchical service scheduling on two identical machines with release times [J]. Operations Research Transactions, 2016, 20(2): 49-58.
[14]	WANG Chengfei, ZHANG Yuzhong. Online batch scheduling with known information in advance [J]. Operations Research Transactions, 2016, 20(1): 84-90.
[15]	YAO Ran, CHEN Guangting, ZHANG An, CHEN Yong. Preemptive online algorithms for scheduling on three machines with hierarchies [J]. Operations Research Transactions, 2013, 17(4): 63-68.

Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 15

Related Articles 15

Recommended Articles

Metrics

Comments