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

AVERAGE-CASE ANALYSIS OF THE MODIFIED HARMONIC algorithm

algorithmICA 1989年第4期4卷 519-533页

作者： RAMANAN, P TSUGA, K 1. Department of Computer Science University of California 93106 Santa Barbara CA USA

In this paper we analyze the average-case performance of the Modified Harmonic algorithm for on-line bin packing. We first analyze the average-case performance for arbitrary distribution of item sizes over (0,1]. This analysis is based on the following result. Letf ₁ andf ₂ be two linear combinations of random variables {N _i} _i=1 ^k where theN _i's have a joint multinomial distribution for eachn=σ _i=1 ^k ,N _i. LetE(f ₁) ≠ O andE(f ₂)≠ 0. Then lim_n _→∞E(max(_f ₁,f ₂))/n = lim_n→∞ max(E(f ₁),E(f ₂))/n. We then consider the special case when the item sizes are uniformly distributed over (0,1]. For specific values of the parameters, the Modified Harmonic algorithm turns out to be better than the other two linear-time on-line algorithms—Next Fit and Harmonic—in both the worst case as well as the average case. We also obtain optimal values for the parameters of the algorithm from the average-case standpoint. For these values of the parameters, the average-case performance ratio is less than 1.19. This compares well with the performance ratios 1.333. and 1.2865. of the Next Fit algorithm and the Harmonic algorithm, respectively.

关键词： Bin packing Approximation algorithm on-line algorithm Worst-case performance Average-case performance

来源：评论

学校读者我要写书评

暂无评论

New results on two-machine flow-shop scheduling with rejection

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第4期31卷 1493-1504页

作者： Zhang, Liqi Lu, Lingfa Li, Shisheng Henan Agr Univ Coll Informat & Management Sci Zhengzhou 450003 Henan Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Zhongyuan Univ Technol Coll Sci Zhengzhou 450007 Henan Peoples R China

In this paper, we consider the off-line and on-line two-machine flow-shop scheduling problems with rejection. The objective is to minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs. For the off-line version, Shabtay and Gasper (Comput Oper Res 39:1087-1096, 2012) showed that this problem is NP-hard and then provided a pseudo-polynomial-time algorithm, two 2-approximation algorithms and a fully polynomial-time approximation scheme. We further study some special cases in this paper. We show that this problem is still NP-hard even when all jobs have the same processing time on one of the machines or all jobs have the same rejection penalty. Furthermore, we also showed that this problem can be solved in polynomialtime algorithm when all jobs satisfy the agreeable condition on their processing times and rejection penalties. For the on-line version without rejection, Chen and Woeginger [in: Du DZ, Pardalos PM (eds.) Minimax and Applications, 1995] showed that the competitive ratio of any determined on-line algorithm is at least 2. We further show that the competitive ratio of any determined on-line algorithm is at least 2 even when all jobs have the same processing time on the first machine. Finally, for the on-line version with rejection, we present a class of on-line algorithms with the best-possible competitive ratio 2.

关键词： Scheduling Flowshop Rejection penalty NP-hard on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

How to find a point on a line within a fixed distance

引用

DISCRETE APPLIED MATHEMATICS 1999年第1期93卷 67-73页

作者： Hipke, C Icking, C Klein, R Langetepe, E Fern Univ Hagen D-58084 Hagen Germany Univ Freiburg Inst Informat D-79110 Freiburg Germany

It is well known that on a line, a target point in unknown position can be found by walking a path at most 9 times as long as the distance from the start to the target point, in the worst case. This competitive factor of 9 is optimal. We investigate the case where the target is known to be within a fixed distance, r, of the start point, and determine the optimum competitive factor, C(r) < 9, that can be achieved by a competitive strategy S(r), under this additional assumption. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithm competitive analysis doubling navigation autonomous vehicle robotics computational geometry

来源：评论

学校读者我要写书评

暂无评论

The polygon exploration problem

引用

SIAM JOURNAL ON COMPUTING 2001年第2期31卷 577-600页

作者： Hoffmann, F Icking, C Klein, R Kriegel, K Free Univ Berlin Inst Informat D-14195 Berlin Germany Fern Univ Hagen D-58084 Hagen Germany Univ Bonn Inst Informat 1 D-53117 Bonn Germany

We present an on-line strategy that enables a mobile robot with vision to explore an unknown simple polygon. We prove that the resulting tour is less than 26.5 times as long as the shortest watchman tour that could be computed off-line. Our analysis is doubly founded on a novel geometric structure called the angle hull. Let D be a connected region inside a simple polygon, P. We de ne the angle hull of D, AH(D), to be the set of all points in P that can see two points of D at a right angle. We show that the perimeter of AH (D) cannot exceed in length the perimeter of D by more than a factor of 2. This upper bound is tight.

关键词： angle hull competitive strategy computational geometry curve length motion planning navigation on-line algorithm optimum watchman tour polygon robot

来源：评论

学校读者我要写书评

暂无评论

On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: Minimizing the makespan and delivery cost

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第3期244卷 704-714页

作者： Han, Bin Zhang, Wenjun Lu, Xiwen Lin, Yingzi E China Univ Sci & Technol Complex & Intelligent Syst Ctr Shanghai 200237 Peoples R China Univ Saskatchewan Dept Mech Engn Saskatoon SK S7N 5A9 Canada Northeastern Univ Dept Mech & Ind Engn Boston MA 02115 USA

This paper investigates minimization of both the makespan and delivery costs in on-line supply chain scheduling for single-machine and parallel-machine configurations in a transportation system with a single customer. The jobs are released as they arrive, which implies that no information on upcoming jobs, such as the release time, processing time, and quantity, is known beforehand to the scheduler. The jobs are processed on one machine or parallel machines and delivered to the customer. The primary objective of the scheduling is time, which is makespan in this case. The delivery cost, which changes due to the varying number of batches (though the cost for each batch is assumed to be the same) in delivery, is also concerned. The goal of scheduling is thus to minimize both the makespan and the total delivery cost This scheduling involves deciding when to process jobs, which machine to process jobs, when to deliver jobs, and which batch to include jobs. We define 10 problems in terms of (1) the machine configuration, (2) preemption of job processing, (3) the number of vehicles, and (4) the capacity of vehicles. These problems (P1, P2,..., P10) have never been studied before in literature. The lower bound for each problem is first proved by constructing a series of intractable instances. algorithms for these problems, denoted by H1, H2,..., H10, respectively, are then designed and a theoretical analysis is performed. The results show that H1, H2, H6, and H7 are optimal ones according to the competitive ratio criterion, while the other algorithms deviate slightly from the optimum. We also design the optimal algorithm for a special case of P5. A case study is provided to illustrate the performance of H5 and to demonstrate the practicality of the algorithms. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Supply chain scheduling on-line algorithm Delivery cost Makespan

来源：评论

学校读者我要写书评

暂无评论

Single machine scheduling with release dates

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2002年第2期15卷 165-192页

作者： Goemans, MX Queyranne, M Schulz, AS Skutella, M Wang, YG MIT Dept Math Cambridge MA 02139 USA CORE Louvain Belgium Univ British Columbia Fac Commerce & Business Adm Vancouver BC V6T 1Z2 Canada MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA Tech Univ Berlin Dept Math D-1000 Berlin Germany Tech Univ Berlin Inst Math Fak Math & Nat Wissensch 2 D-10623 Berlin Germany Peoplesoft Inc Pleasanton CA 94588 USA

We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completion-time formulation. We show their equivalence by proving that a O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective function value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concept of common and independent alpha-points, respectively. The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least e/(e-1) approximate to 1.5819. Both algorithms may be derandomized;their deterministic versions run in O(n(2)) time. The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards.

关键词： approximation algorithm LP relaxation scheduling on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling of parallel machines to minimize total completion times

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第9期36卷 2647-2652页

作者： Liu, Peihai Lu, Xiwen E China Univ Sci & Technol Sch Sci Shanghai 200237 Peoples R China

In this paper, we consider the scheduling problem on identical parallel machines, in which jobs are arriving over time and preemption is not allowed. The goal is to minimize the total completion times. According to the idea of the Delayed-SPT algorithm proposed by Hoogeven and Vestjens [Optimal on-line algorithms for single-machine scheduling. In: Proceedings 5th international conference on integer programming and combinatorial optimization (IPCO). Lecture notes in computer science, vol. 1084. Berlin: Springer;1996. p. 404-14], we give an on-line algorithm for the scheduling problem on m identical parallel machines. We show that this algorithm is 2-competitive and the bound is tight. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Parallel machine scheduling Analysis of algorithm on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

On-line supply chain scheduling problems with preemption

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2007年第1期181卷 500-504页

作者： Averbakh, Igor Xue, Zhihui Univ Toronto Div Management Scarborough ON M1C 1A4 Canada

We consider supply chain scheduling problems where customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information on the number, release and processing times of future jobs;the processing time of a job becomes known when the job is released. Preemption is allowed. To reduce the total costs, processed jobs are grouped into batches, which are delivered to customers as single shipments;we assume that the cost of delivering a batch does not depend on the number of jobs in the batch. The objective is to minimize the total cost, which is the sum of the total flow time and the total delivery cost. For the single-customer problem, we present an on-line two-competitive algorithm, and show that no other on-line algorithm can have a better competitive ratio. We also consider an extension of the algorithm for the case of m customers, and show that its competitive ratio is not greater than 2m if the delivery costs to different customers are equal. (c) 2006 Elsevier B.V. All rights reserved.

关键词： scheduling combinatorial optimization on-line algorithm supply chain competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Solution to a problem of Nicolas Lichiardopol

引用

DISCRETE MATHEMATICS 2010年第2期310卷 360-363页

作者： Philpotts, Adam R. Waters, Robert J. Univ Bristol Dept Math Bristol BS8 1TW Avon England Univ Nottingham Sch Math Sci Nottingham NG7 2RD England

关键词： On-line sorting on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

A note on on-line scheduling with partial information

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2002年第3-4期44卷 539-543页

作者： Zhang, GC Ye, DS Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China

We consider a variant of on-line scheduling, where partial information on future jobs is known beforehand. Assume that the last job will be the longest (with the longest execution time). We provide the best possible on-line algorithms with competitive ratios root2 and 3/2, respectively, for m = 2 and 3, where m. is the number of machines. (C) 2002 Elsevier Science Ltd. All rights reserved.

关键词： machine scheduling competitive analysis on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：