Search

Abstract: This paper considers two semi-online scheduling problems, one with known optimal value and the other with known total sum, on two uniform machines with a machine speed ratio of . For the first problem, we provide an optimal algorithm for , and improved algorithms or/and lower bounds for , over which the optimal algorithm is unknown. As a result, the largest gap between the competitive ratio and the lower bound decreases to 0.02192. For the second problem, we also present algorithms and lower bounds for . The largest gap between the competitive ratio and the lower bound is 0.01762, and the length of the interval over which the optimal algorithm is unknown is 0.47382. Our algorithms and lower bounds for these two problems provide insights into their differences, which are unusual from the viewpoint of the known results on these two semi-online scheduling problems in the literature. [Copyright &y& Elsevier]

This paper investigates two different semi-online versions of the machine covering, which is the problem of assigning a set of jobs to a system of m(m ⩾ 3) identical parallel machines so as to maximize the earliest machine completion time. In the first case, we assume that the largest processing times is known in advance. In the second case, we assume that the total processing times of all jobs is known in advance. For each version we propose a semi-online algorithm and investigate its competitive ratio. The competitive ratio of each algorithm is (Multiple line equation(s) cannot be represented in ASCII text) which is shown to be the best possible competitive ratio for each semi-online problem. [ABSTRACT FROM AUTHOR]

Abstract: In semi-online scheduling problems, we always assume that some partial additional information is exactly known in advance. This may not be true in some applications. This paper considers semi-online scheduling problems on two identical machines with inexact partial information. Three versions are considered, where we know in advance that the total size of all jobs, the optimal value, and the largest job size are in given intervals, respectively, while their exact values are unknown. We give both lower bounds of the problems and competitive ratios of algorithms as functions of a so-called disturbance parameter . We establish for which the inexact partial information is useful to improve the performance of a semi-online algorithm with respect to its pure online problem. Optimal or near optimal algorithms are then obtained. [Copyright &y& Elsevier]

A general algorithm, called ALG, for online and semi-online scheduling problem Pm∣∣Cmax with m ≥ 2 is introduced. For the semi-online version, it is supposed that all job have their processing times within the interval [p, rp], where p > 0 1 < r ≤ m/m - 1. ALG is a generalization of LS and is optimal in the sense that there is not an algorithm with smaller competitive ratio than that of ALG. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates the semi-online version of scheduling problem on a three-machine system. We assume that all jobs have their processing times between p and rp (). We give a comprehensive competitive ratio of LS algorithm which is a piecewise function on . It shows that LS is an optimal semi-online algorithm for every , and . We further present an optimal algorithm for every , and an almost optimal algorithm for every where the largest gap between its competitive ratio and the lower bound of the problem is at most 0.01417. We also present an improved algorithm with smaller competitive ratio than that of LS for every . [Copyright &y& Elsevier]

Abstract: In this paper, we consider an ordinal on-line scheduling problem. A sequence of n independent jobs has to be assigned non-preemptively to two uniformly related machines. We study two objectives which are maximizing the minimum machine completion time, and minimizing the l p norm of the completion times. It is assumed that the values of the processing times of jobs are unknown at the time of assignment. However it is known in advance that the processing times of arriving jobs are sorted in a non-increasing order. We are asked to construct an assignment of all jobs to the machines at time zero, by utilizing only ordinal data rather than actual magnitudes of jobs. For the problem of maximizing the minimum completion time we first present a comprehensive lower bound on the competitive ratio, which is a piecewise function of machine speed ratio s. Then, we propose an algorithm which is optimal for any s ⩾1. For minimizing the l p norm, we study the case of identical machines (s =1) and present tight bounds as a function of p. [Copyright &y& Elsevier]

The optimization versions of the k-PARTITIONING problems are considered in this paper. For the objective to maximize the minimum load of m subsets, we first show that the FOLDING algorithm has a tight worst case ratio of max{2/k,1/m}. Then, we present an algorithm called HARMONIC1 with a worst case ratio at least max{ 1/k, 1/(⌈Σi=1m 1/i ⌉ +1)}. It concludes the HARMONIC1 is better than FOLDING for k > 2(⌈ Σi=1m 1/i ⌉ + 1). We further show that HARMONICI is asymptotically optimal ordinal algorithm. We also present an algorithm HARMONIC2 for solving the general κi-PARTITIONING problem. [Copyright &y& Elsevier]

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently Imreh and Nogaproposed to add the concept of machine cost to scheduling problems and considered the so-called List Model problem. An online algorithm with a competitive ratio 1.618 was given while the lower bound is 4/3. In this paper, two different semi-online versions of this problem are studied. In the first case, it is assumed that the processing time of the largest job is known a priori. A semi-online algorithm is presented with the competitive ratio at most 1.5309 while the lower bound is 4/3. In the second case, it is assumed that the total processing time of all jobs is known in advance. A semi-online algorithm is presented with the competitive ratio at most 1.414 while the lower bound is 1.161. It is shown that the additional partial available information about the jobs leads to the possibility of constructing a schedule with a smaller competitive ratio than that of online algorithms. [ABSTRACT FROM AUTHOR]

The optimization versions of the 3-Partitioning and the Kernel 3-Partitioning problems are considered in this paper. For the objective to maximize the minimum load of the m subsets, it is shown that the MODIFIED LPT algorithm has performance ratios (3 m − 1)/(4 m − 2) and (2 m − 1)/(3 m − 2), respectively, in the worst case. [ABSTRACT FROM AUTHOR]