Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines

This paper investigates two preemptive semi-online scheduling problems to minimize makespan on two uniform machines. In the first semi-online problem, we know in advance that all jobs have their processing times in between p and rp . In the second semi-online problem, we know the size of the largest job in advance. We design an optimal semi-online algorithm which is optimal for every combination of machine speed ratio and job processing time ratio for the first problem, and an optimal semi-online algorithm for every machine speed ratio for the second problem.Received: 2 December 2003, Published online: 16 January 2004This research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China, and National Natural Science Foundation of China (10271110).     

Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines

In this paper, we consider semi-online minimum makespan scheduling problem with reassignment on two identical machines. Two versions are discussed. In the first version, one can reassign the last job of one machine that is based on the problem proposed by Tan and Yu (2008) [1], in which case the last job of each machine is allowed to be reassigned. An optimal algorithm which has the same competitive ratio is presented. In the second version we consider the combination of the next two conditions: the total size of all jobs is known in advance and one can reassign the last job of one machine. For this problem an optimal algorithm with competitive ratio is also given.     

Optimal preemptive semi-online scheduling on two uniform processors

We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1,r] (r?1) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s?1, respectively. The objective is to minimize makespan. We characterize the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm along with a matching lower bound, which also holds for randomized algorithms.     

Preemptive stochastic online scheduling on two uniform machines

This paper addresses a stochastic online scheduling problem in which a set of independent jobs are to be processed by two uniform machines whose speeds are 1 and s(s?1). Each job has a processing time, which is a random variable with an arbitrary distribution, and all the jobs are arriving overtime, which means that no information of the job is known in advance before its arrival. During the processing, jobs are allowed to be preempted and resumed later. The objective is to minimize the sum of expected weighted completion times. In this paper, the optimal policy, named SMPR, is designed for the single-machine preemptive stochastic scheduling problem where jobs have a common arriving time. Based on SMPR, the online approximative policy-UMPR, is devised for the preemptive stochastic online scheduling on two uniform machines. Then, UMPR is proved to have an approximation factor of 2. Furthermore, it is concluded that UMPR could not have a smaller approximation factor than 2, which means 2 is the approximation ratio of UMPR for the two-uniform-machine scheduling problem.     

Online scheduling on two uniform machines subject to eligibility constraints

We consider the online scheduling of a set of jobs on two uniform machines with the makespan as objective. The jobs are presented in a list. We consider two different eligibility constraint set assumptions, namely (i) arbitrary eligibility constraints and (ii) Grade of Service (GoS) eligibility constraints. In the first case, we prove that the High Speed Machine First (HSF) algorithm, which assigns jobs to the eligible machine that has the highest speed, is optimal. With regard to the second case, we point out an error in [M. Liu et al., Online scheduling on two uniform machines to minimize the makespan, Theoretical Computer Science 410 (21–23) (2009) 2099–2109]; we then provide tighter lower bounds and present algorithms with worst-case analysis for various ranges of machine speeds.     

A note on MULTIFIT scheduling for uniform machines

In this note, we derive the tight worst case bound √6/2+(1/2) ^k for scheduling with the MULTIFIT heuristic on two parallel uniform machines withk calls of FFD within MULTIFIT. When MULTIFIT is combined with LPT as an incumbent algorithm the worst case bound decreases to √2+1/2+(1/2) ^k . Partially supported by SFB F003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung and by the National Natural Science Foundation of China, Grant 19701028.     

Approximation for scheduling on uniform nonsimultaneous parallel machines

We consider the problem of scheduling on uniform machines which may not start processing at the same time with the purpose of minimizing the maximum completion time. We propose using a variant of the MULTIFIT algorithm, LMULTIFIT, which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within \(\sqrt{6}/2\) times the optimal maximum completion time for problem instances with two machines. Both developments represent improvements over previous results. We prove that LMULTIFIT worst-case bounds for scheduling on simultaneous uniform machines are also LMULTIFIT worst-case approximation bounds for scheduling on nonsimultaneous uniform machines and show that worst-case approximation bounds of MULTIFIT variants for simultaneous uniform machines from previous literature also apply to LMULTIFIT. We also comment on how a PTAS for scheduling on a constant number of uniform machines with fixed jobs can be used to obtain a PTAS for scheduling on a constant number of uniform nonsimultaneous parallel machines.     

Batch scheduling on uniform machines to minimize total flow-time

The solution of the classical batch scheduling problem with identical jobs and setup times to minimize flowtime is known for twenty five years. In this paper we extend this result to a setting of two uniform machines with machine-dependent setup times. We introduce an O(n) solution for the relaxed version (allowing non-integer batch sizes), followed by a simple rounding procedure to obtain integer batch sizes.     

Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information

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 application. This paper considers semi-online problems on identical machines with inexact partial information. Three problems are considered, where we know in advance that the optimal value, or 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 r ∈[1, ∞). We establish for which r the inexact partial information is useful to improve the performance of a semi-online algorithm with respect to its pure online problem. Optimal preemptive semi-online algorithms are then obtained. Research supported by Natural Science Foundation of China (10671177) and Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in proceedings of ISAAC’05.     

Preemptive scheduling on uniform machines to minimize mean flow time

A set of jobs has to be scheduled on parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing at its release date. All jobs have the same execution requirement, and each machine has a known speed. The processing of any job may be interrupted arbitrarily often and resumed later on any machine. We want to find a schedule that minimizes the sum of completion times, i.e., we consider problem Q|_rj,_pj=p,pmtn|∑_Cj$Q|r_j,p_j=p,\mathrm{pmtn}|\sum C_j$ whose complexity status was open. In this paper, we give a polynomial algorithm for the above problem. The algorithm is based on a reduction of the scheduling problem to a linear program. The crucial condition for implementing the proposed reduction is the known order of job completion times.     

A parallel algorithm for preemptive scheduling of uniform machines

In this paper we describe a fast parallel algorithm for preemptive scheduling of n independent jobs on m uniform machines. Each job has a processing requirement, and each machine processes jobs at a different rate. The goal of the scheduling algorithm is to find a schedule which minimizes the time at which the last job is completed. T. Gonzalez and S. Sahni have developed a sequential algorithm which solves this problem in O(n + m log m) time. We develop a parallel version of this algorithm for a Concurrent Read Exclusive Write (CREW) shared memory computer. The algorithm runs in O(log n + log³m) time using n processors.     

Improved optimal algorithms for scheduling unit-length independent tasks on uniform machines

Five scheduling problems are considered, concerning unit-length independent tasks and uniform machines. New improved optimal algorithms are presented that can solve these problems in at most O( n log n) time, where n is the number of tasks. The existing algorithms solve most of these problems in O( n ³ ) time. Proofs of optimality of the present algorithms are included, and simple representative examples are provided that illustrate the type of results obtained     

Semi-online scheduling problems on a small number of machines

We consider the semi-online parallel machine scheduling problem of minimizing the makespan given a priori information: the total processing time, the largest processing time, the combination of the previous two or the optimal makespan. We propose a new algorithm that can be applied to the problem with the known total or largest processing time and prove that it has improved competitive ratios for the cases with a small number of machines. Improved lower bounds of the competitive ratio are also provided by presenting adversary lower bound examples.