检索结果-内蒙古大学图书馆

online Scheduling on a Bounded Batch Machine with Same-Length-Job Families

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2025年

作者： Wang, Libo Li, Wenhua Chai, Xing Gao, Yanhong Yu, Dan Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Henan Univ Technol Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

We investigate an online scheduling problem on a bounded batch machine with f incompatible job families, in which the jobs are released over time and the jobs belonging to the same family have the same processing times. The goal is to minimize the maximum completion time. A machine can process at most b jobs simultaneously as a batch, where b is finite. A batch only contains the jobs from the same family. KRT setting means that no job is released when the machine is busy. In this paper, we consider the above model under two environments: (1) KRT setting and (2) general setting. In the KRT setting, we provide the lower bounds 1 +root f(2) -f+1-1 /(f) for b >= f and min {(2f+1)/ (f+2) , (2b )/(b+1)} for 2 <= b < f. In the general setting, we provide the lower bounds 1 + root 4f(2) +1-1/ (2f) for b >= f + 1 and (2b)/( b+1) for 2 <= b < f + 1. We further present an online algorithm, which is the best possible when b >= f for the KRT setting and when b >= f + 1 for the general setting.

关键词： online algorithm bounded batch incompatible job families KRT setting competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online Unbounded Knapsack

引用

THEORY OF COMPUTING SYSTEMS 2025年第1期69卷 1-25页

作者： Boeckenhauer, Hans-Joachim Gehnen, Matthias Hromkovic, Juraj Klasing, Ralf Komm, Dennis Lotze, Henri Mock, Daniel Rossmanith, Peter Stocker, Moritz Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany Univ Bordeaux CNRS LaBRI Talence France

We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of n items with a size and a value each, and an algorithm has to decide whether or not and how often to pack each item into a knapsack of bounded capacity. The items are given online and the total size of the packed items must not exceed the knapsack's capacity, while the objective is to maximize the total value of the packed items. While each item can only be packed once in the classical knapsack problem (also called the 0-1 knapsack problem), the unbounded version allows for items to be packed multiple times. We show that the simple unbounded knapsack problem, where the size of each item is equal to its value, allows for a competitive ratio of 2. We also analyze randomized algorithms and show that, in contrast to the 0-1 knapsack problem, one uniformly random bit cannot improve an algorithm's performance. More randomness lowers the competitive ratio to less than 1.736, but it can never be below 1.693. In the advice complexity setting, we measure how many bits of information (so-called advice bits) the algorithm has to know to achieve some desired solution quality. For the simple unbounded knapsack problem, one advice bit lowers the competitive ratio to 3/2. While this cannot be improved with fewer than loglog22nn advice bits for instances of length n, a competitive ratio of 1 + epsilon can be achieved with O(epsilon(-1 ) log(n epsilon(-1))) advice bits for any epsilon > 0. We further show that no amount of advice bounded by a function f(n) allows an algorithm to be optimal. We also study the online general unbounded knapsack problem and show that it does not allow for any bounded competitive ratio for both deterministic and randomized algorithms, as well as for algorithms using fewer than log(2)n advice bits. We also provide a surprisingly simple algorithm that uses O(epsilon(-1 ) log(n epsilon(-1))) advice

关键词： online knapsack Unbounded knapsack online algorithm Advice complexity

来源：评论

学校读者我要写书评

暂无评论

Competitive algorithms for the online Minimum Peak Job Scheduling

引用

OPERATIONS RESEARCH 2025年第1期73卷 iii-vii, 1-582, C2-C3页

作者： Escribe, Celia Hu, Michael Levi, Retsef MIT Operat Res Ctr Cambridge MA 02139 USA Massachusetts Gen Hosp Hlth Syst Engn Boston MA 02114 USA MIT Sloan Sch Management Cambridge MA 02139 USA

This paper describes a fundamental online scheduling problem called the minimum peak job scheduling (MPJS) problem. In this problem, there is a sequence of arriving jobs, each with a specified required scheduled time for one unit of a scarce and reusable resource. The goal is to schedule each job upon arrival within a scheduling interval to minimize the resulting peak utilization (i.e., the maximum number of units used simultaneously throughout the entire scheduling interval). The MPJS problem captures many practical settings of real-time appointment scheduling. Its offline version where all jobs are known in advance is equivalent to the well-known bin-packing problem, where jobs correspond to items and the unit resource is a bin. However, the online variant of MPJS allows additional flexibility in that initially, one only commits to the scheduling time, but the allocation to the resources can be done later. In the bin-packing problem, this corresponds to the ability to move items across bins. Some relaxed versions of online bin-packing problems have already been studied, but none fundamentally capture the MPJS model studied in this paper. The paper describes the first competitive online algorithm to the MPJS problem called the harmonic rematching (HR) algorithm. The analysis shows that the HR algorithm has an asymptotic competitive ratio below 1.5. The fact that the current best lower bound on randomized online algorithms for the bin-packing problem is 1.536 highlights the fundamental difference between these two related models.

关键词： bin packing online algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online scheduling problem of incompatible batch processing with deterioration effect and delivery time in the steel rolling process

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2025年第3期76卷 454-465页

作者： Ma, Ran Meng, Lanmeng Zhang, Yuzhong Qingdao Univ Technol Qingdao Peoples R China Qufu Normal Univ Rizhao Peoples R China

As market competition intensifies, modern enterprises prioritize customer demands, leading to an increased emphasis on multi-variety and small-batch production. In this article, we study the online scheduling problem for incompatible batch processing with the deterioration effect to minimize the maximum delivery completion time in the billet rolling process, where the batch capacity and delivery capacity are unbounded. We assume that the processing time of job J(j )is expressed as p(j )= a(j)(A + Bt), where A > 0, B > 0, t denotes the start time of job and a(j) > 0 represents the job's processing deterioration rate. For such an online problem, we first prove that the lower bound of the problem is (1+Ba-max)(k), where k denotes the number of job families and a(max )represents the maximum deterioration ratio in job instance. Then we design an online algorithm Largest Delivery Time With Batch Processing and demonstrate that the competitive ratio of the algorithm is no more than 1+(1+Ba-max)(k). Finally, experiments on randomly generated instances prove that our algorithm is reasonable and effective.

关键词： Scheduling online algorithm incompatible batch deteriorating effects delivery time

来源：评论

学校读者我要写书评

暂无评论

Optimal algorithms for online batch scheduling with all possible equal-processing times under periodic pulse interruptions

引用

DISCRETE APPLIED MATHEMATICS 2025年 370卷 71-83页

作者： Lin, Ran Feng, Huiyan Li, Wenhua Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

We address an online scheduling problem on a batch machine to minimize the makespan. Jobs are released online over time and can be grouped into batches simultaneously with equal-processing times. This batch machine has periodic pulse interruptions, which are machine unavailable periods with negligible length. The pulse interruptions divide the scheduling horizon into periodic available intervals. A batch can be processed only within an available interval without any preemption. For all possible equal-processing times, we develop the lower bounds on competitive ratios and provide optimal online algorithms when the batch capacity is unbounded and bounded, respectively. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Scheduling online algorithm Batch machine Competitive ratio Pulse interruption

来源：评论

学校读者我要写书评

暂无评论

online Bottleneck Matching on a Ring 42nd

Online Bottleneck Matching on a Ring

引用

42nd National Conference on Theoretical Computer Science

作者： Xiao, Man Li, Weidong Yunnan Univ Sch Math & Stat Kunming 650504 Yunnan Peoples R China

ISBN: (纸本)9789819614899;9789819614905

On a ring, given m servers and m requests arriving one by one in an online fashion. Upon each request arrival, it needs to be immediately matched to a server, generating a matching distance on the ring. The objective is to find a matching where each server and each request are strictly matched once, minimizing the maximum matching distance. When the m servers are evenly distributed on the ring, we prove that the classical greedy algorithm achieves an optimal competitive ratio of m. When m = 3, using polar coordinates to partition the ring into three intervals, we provide optimal online algorithms for four parameter scenarios where the competitive ratio depends on the server spacing ratio.

关键词： online bottleneck matching Ring Partition online algorithm

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling with the learning effect of processing time and the deterioration effect of delivery time for prefabricated components

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第3期49卷 1-26页

作者： Li, Na Ma, Ran Zhang, Yuzhong Qingdao Univ Technol Sch Management Engn Qingdao 266520 Peoples R China Qufu Normal Univ Inst Operat Res Sch Management Rizhao 276826 Peoples R China

In the production scheduling of prefabricated components, a scheduling model considering the learning effect of processing time and the deterioration effect of delivery time in this paper is provided. More precisely, it asks for an assignment of a series of independent prefabricated jobs that arrived over time to a single machine for processing, and once the execution of a job is finished, it will be transported to the destination. The information of each prefabricated job including its basic processing time bj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_{j}$$\end{document}, release time rj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_j$$\end{document}, and deterioration rate ej\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e_j$$\end{document} of delivery time is unknown in advance and is revealed upon the arrival of this job. Moreover, the actual processing time of prefabricated job Jj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J_j$$\end{document} with learning effect is pj=bj(a-bt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_{j}=b_{j}(a-b t)$$\end{docum

关键词： Scheduling online algorithm Single machine Learning effect Prefabricated components

来源：评论

学校读者我要写书评

暂无评论

online algorithms for scheduling with machine activation cost on two uniform machines

引用

Journal of Zhejiang University-Science A(Applied Physics & Engineering) 2007年第1期8卷 127-133页

作者： HAN Shu-guang JIANG Yi-wei HU Jue-liang Department of Mathematics Zhejiang University Hangzhou 310027 China Faculty of Science Zhej iang Sci- Tech University Hangzhou 310018 China

In this paper we investigate a variant of the scheduling problem on two uniform machines with speeds 1 and s. For this problem, we are given two potential uniform machines to process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed, the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and the machine activation cost. We design optimal online algorithms with competitive ratio of (2s+1)/(s+1) for every s≥1.

关键词： online algorithm Competitive analysis Uniform machine scheduling Machine activation cost

来源：评论

学校读者我要写书评

暂无评论

online algorithms for the multiple time series search problem

引用

COMPUTERS & OPERATIONS RESEARCH 2012年第5期39卷 929-938页

作者： Zhang, Wenming Xu, Yinfeng Zheng, Feifeng Dong, Yucheng Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China NW Univ Xian Sch Econ & Management Xian 710069 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China Minist Educ Key Lab Proc Control & Efficiency Engn Xian 710049 Peoples R China

This work investigates the online multiple time series search problem. Given a storage with finite capability, a player receives one product for sale and observes a selling price as well at each period. With the knowledge that prices in all periods vary within [m,M] (0 < m < M), the player decides at the period whether to sell some of the products in the storage together with the one currently received at the price observed or to store the current one in the storage. Our main contributions are three online algorithms TRPP, SOEP and IS where IS is a combination of TRPP and SOEP, and their competitiveness analyses. Moreover, we prove a lower bound of the competitive ratio for the problem, and prove that 7S is optimal as the ratio M/m goes to infinity. Numerical computation further shows that the gap between the upper and lower bounds first increases and then decreases as M/m rises. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Time series search online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online algorithms for the mixed ring loading problem with two nodes

引用

OPTIMIZATION LETTERS 2021年第4期15卷 1229-1239页

作者： Guan, Li Li, Weidong Xiao, Man Yunnan Univ Sch Math & Stat Kunming 650504 Yunnan Peoples R China

In this paper, we introduce the mixed ring loading problem, where the ring contains undirected and bidirected links. When the ring consists of two nodes, we consider the online mixed ring loading problem under three different scenarios including splittable, integer splittable and unsplittable. When the demands are (integer) splittable, we present an (asymptotically) optimal online algorithm. When the demands are unsplittable, we present an online algorithm which generalizes the previous result.

关键词： Ring loading online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：