In this paper, we consider the on-line single machine scheduling of unit time jobs with rejection. All jobs arrive on-line over a list (one by one). For each arriving job, the on-line algorithm must decide immediately...
详细信息
In this paper, we consider the on-line single machine scheduling of unit time jobs with rejection. All jobs arrive on-line over a list (one by one). For each arriving job, the on-line algorithm must decide immediately to accept or reject it. The objective is to minimize the maximum quadratic completion time of accepted jobs plus the total rejection cost of rejected jobs. For this problem, we show that 1.7299 is a lower bound on the competitive ratio and present a simple greedy algorithm with the competitive ratio 2. Furthermore, we also provide a modified greedy algorithm with a better competitive ratio 1 + root 3/2 approximate to 1.86602.
We consider the problem of scheduling jobs on-line on batch processing machines with dynamic job arrivals to minimize makespan. A batch processing machine can handle up to B jobs simultaneously. The jobs that are proc...
详细信息
We consider the problem of scheduling jobs on-line on batch processing machines with dynamic job arrivals to minimize makespan. A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on-line algorithms with worst-case ratio (root5 + 1)/2 (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst-case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bounds are given, and two on-line algorithms are presented. (C) 2001 John Wiley B Sons, Inc. Naval Research Logistics 48: 241-258, 2001.
A manufacturer has to process jobs released on-line and deliver them to customers. Preemption is allowed. Jobs are grouped into batches for delivery. The sum of the total flow time and the total delivery cost is minim...
详细信息
A manufacturer has to process jobs released on-line and deliver them to customers. Preemption is allowed. Jobs are grouped into batches for delivery. The sum of the total flow time and the total delivery cost is minimized. Deliveries to different customers cannot be combined. We present an on-line algorithm with the competitive ratio bounded by 3 + alpha, where alpha is the ratio of the largest processing time to the smallest processing time. (C) 2013 Elsevier B.V. All rights reserved.
We deal with the variable-sized bin covering problem: Given a list L of items in (0, 1] and a finite collection B of feasible bin sizes, the goal is to select a set of bins with sizes in B and to cover them with the i...
详细信息
We deal with the variable-sized bin covering problem: Given a list L of items in (0, 1] and a finite collection B of feasible bin sizes, the goal is to select a set of bins with sizes in B and to cover them with the items in L such that the total size of the covered bins is maximized. In the on-line version of this problem, the items must be assigned to bins one by one without previewing future items. This note presents a complete solution to the on-line problem: For every collection B of bin sizes, we give an on-line approximation algorithm with a worst-case ratio r(B), and we prove that no on-line algorithm can perform better in the worst case. The value r(B) mainly depends on the largest gap between consecutive bin sizes. (C) 1999 Elsevier Science B.V. All rights reserved.
In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1 + phi)p], where p > 0 and phi = (root 5-1)/2. Jobs arrive over time. Fi...
详细信息
In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1 + phi)p], where p > 0 and phi = (root 5-1)/2. Jobs arrive over time. First, we deal with the on-line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio (root 5 + 1)/2 are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on-line algorithms with competitive ratio (root 5+ 1)/2. The two class of algorithms are optimal for the problems studied here.
A simple polygon P with two distinguished vertices s and t is said to be a street if the clockwise and counterclockwise boundary of P from s to t are mutually weakly visible. We consider the problem of traversing a pa...
详细信息
A simple polygon P with two distinguished vertices s and t is said to be a street if the clockwise and counterclockwise boundary of P from s to t are mutually weakly visible. We consider the problem of traversing a path from s to t in an unknown street P for a mobile robot with on-board vision system such that the number of links in the path is as small as possible. To our knowledge, this problem has not been studied before. We present an algorithm for this problem that requires at most 2m - 1 links to reach from s to t, where m denotes the link distance between s and t in P. Hence the competitive ratio of our algorithm is 2 - 1/m. We also show that any on-line algorithm for the above problem will require 2m - 1 links in the worst case which establishes that our algorithm is optimal. We next consider the above problem for the special case when P is a rectilinear street and the path is required to be a rectilinear path. We propose an algorithm for this problem that requires at most m+1 links to reach from s to t, where m denotes the rectilinear link distance between s and t in P. Hence the competitive ratio of our algorithm is if 1/m. We also show that any on-line algorithm for this problem will require m + 1 links in the worst case which establishes that our algorithm is optimal. (C) 1997 Elsevier Science B.V.
A version of the k-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive a...
详细信息
A version of the k-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive an algorithm with worst-case performance bound 1.7 for k≥3.
An on-line algorithm is developed for the location of single cross point faults in a PLA (FPLA). The main feature of the algorithm is the determination of a fault set corresponding to the response obtained for a faile...
详细信息
An on-line algorithm is developed for the location of single cross point faults in a PLA (FPLA). The main feature of the algorithm is the determination of a fault set corresponding to the response obtained for a failed test. For the apparently small number of faults in this set, all other tests are generated and a fault table is formed. Subsequently, an adaptive procedure is used to diagnose the fault. Functional equivalence test is carried out to determine the actual fault class if the adaptive testing results in a set of faults with identical tests. The large amount of computation time and storage required in the determination, a priori, of all the fault equivalence classes or in the construction of a fault dictionary are not needed here. A brief study of functional equivalence among the cross point faults is also made.
We consider bi-directional non-preemptive conversion with interrelated conversion rate bounds. We solve this conversion problem with two on-line algorithms BUND and RUN and give their competitive ratio. We further obs...
详细信息
In this paper, the authors consider an on-line scheduling problem of rn （m≥ 3） identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance tim...
详细信息
In this paper, the authors consider an on-line scheduling problem of rn （m≥ 3） identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive 1 ratio 4 - 1/m. In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is 10/3.
暂无评论