On-Line Scheduling for Jobs with Arbitrary Release Times on Parallel Related Uniform Machines

A parallel related uniform machine system consists of m machines with different processing speeds. The speed of any machine is independent on jobs. In this paper, we consider online scheduling for jobs with arbitrary release times on the parallel uniform machine system. The jobs appear over list in terms of order. An order includes the processing size and releasing time of a job. For this model, an algorithm with competitive ratio of 12 is addressed in this paper.

Online algorithms for scheduling with machine activation cost on two uniform machines

In this paper we investigate a variant of the scheduling problem on two uniform machines with speeds 1 and s. For this problem, we are given two potential uniform machines to process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed, the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and the machine activation cost. We design optimal online algorithms with competitive ratio of (2s+1)/(s+1) for every s≥1.

Optimal Preemptive Online Algorithms for Scheduling with Known Largest Size on Two Uniform Machines

In this paper, we consider the seml-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time （starting from time zero） when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ [1, ∞）, and show that idle time is required to achieve the optimality during the assignment procedure of the algorithm for any s 〉 （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）. The competitive ratio of the algorithms is （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）, which matches the randomized lower bound for every s ≥ 1. Hence randomization does not help for the discussed preemptive scheduling problem.

An Optimal Online Algorithm for Fractional Scheduling on Uniform Machines with Three Hierarchies

This paper is concerned with the fractional version of online hierarchical scheduling problem on uniform machines.In the problem,the jobs and machines have several different hierarchies and each job can be arbitrarily split between the machines with hierarchies not above the hierarchy of the job.The objective is to minimize the makespan.The authors present an optimal algorithm for the problem with three hierarchies.

ON-LINE SCHEDULING OF UNIT TIME JOBS WITH REJECTION ON UNIFORM MACHINES

The authors consider the problem of on-line scheduling of unit execution time jobs on uniform machines with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected. The objective is to minimize the total completion time of the accepted jobs and the total penalty of the rejection jobs. The authors propose an on-line algorithm and prove that the competitive ratio is 1/2 （2 W √3） ≈ 1.86602.

A Modified Differential Evolution for Uniform Parallel Machines Scheduling Problem with Minimizing Makespan

The problem of scheduling jobs on uniform parallel machines with makespan ( C max ) minimization objective was studied. Due to its non-deterministic polynomial-time ( N ) hard nature,it is difficult to achieve an optimal solution with traditional optimization methods. For this reason,a novel modified differential evolution ( MDE) was proposed to tackle the uniform parallel machine scheduling problem ( UPMSP ) ,taking out the mutation operation and introducing the roulette wheel selection strategy into conventional differential evolution ( DE ) . In MDE, more high quality individuals can be reserved to update the population. And the control parameter F in conventional DE was removed,which could simplify the DE. To verify the proposed MDE,162 randomly generated instances were conducted. The comparison results with DE,genetic algorithm ( GA ) ,simulated annealing ( SA ) , and largest processing time ( LPT) method show that the MDE is an efficient and competitive approach in solving UPMSP.

Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan

We study an online(over time)scheduling problem on two uniform unbounded parallel-batch machines with processing speed 1 and v(0<≤1),respectively,to minimize the makespan.We first show that no online algorithm can have a competitive ratio less than 1+αL,whereαL=(√5−1)/2≈0.618 if 0≤1/2,andαL=α2(v)is the positive root ofα^(3)+3α^(2)+(3−1/v)α−1/v=0 if1/2≤1.This lower bound is still valid when all jobs have the same processing times.Then,we provide an online algorithm with a competitive ratio at most min{(√5+1)/2,√2/v}.When the jobs have the same processing times,we present the best possible online algorithm with a competitive ratio 1+αL.

Uniform Parallel-Machine Scheduling with Time Dependent Processing Times

We consider several uniform parallel-machine scheduling problems in which the processing time of a job is a linear increasing function of its starting time.The objectives are to minimize the total completion time of all jobs and the total load on all machines.We show that the problems are polynomially solvable when the increasing rates are identical for all jobs;we propose a fully polynomial-time approximation scheme for the standard linear deteriorating function,where the objective function is to minimize the total load on all machines.We also consider the problem in which the processing time of a job is a simple linear increasing function of its starting time and each job has a delivery time.The objective is to find a schedule which minimizes the time by which all jobs are delivered,and we propose a fully polynomial-time approximation scheme to solve this problem.

UNIFORM MACHINE SCHEDULING WITH MACHINE AVAILABLE CONSTRAINTS

In this paper, we consider a uniform machine scheduling problem with nonsimultaneous available times. We prove that LPT algorithm has a worst case bound in the interval (1.52,5/3). We tighten this bound when the machine speed ratio is small or m=2. Furthermore, we present a linear compound algorithm QLC with a worst case bound of 6/5 for a two-machine system.