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...
详细信息
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 1 andf 2 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 1) ≠ O andE(f 2)≠ 0. Then limn→∞E(max(f1,f 2 ))/n = lim n →∞ max(E(f 1),E(f 2))/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.
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 re...
详细信息
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.
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...
详细信息
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.
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...
详细信息
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.
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....
详细信息
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.
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 ...
详细信息
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.
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 th...
详细信息
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.
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 ...
详细信息
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.
We present a solution to a problem posed by Nicolas Lichiardopol, regarding the on-line sorting of a sequence of integers. (C) 2008 Elsevier B.V. All rights reserved.
We present a solution to a problem posed by Nicolas Lichiardopol, regarding the on-line sorting of a sequence of integers. (C) 2008 Elsevier B.V. All rights reserved.
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 o...
详细信息
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.
暂无评论