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 ...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.展开更多
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. Ma...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.展开更多
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...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.展开更多
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 o...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.展开更多
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 bot...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.展开更多
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 opti...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.展开更多
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 machi...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.展开更多
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 a...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.展开更多
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...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.展开更多
文摘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.
基金Project (No. Y605316) supported by the Natural Science Foundationof Zhejiang Province, China and the Natural Science Foundation of the Education Department of Zhejiang Province (No. 20060578), China
文摘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.
基金supported by National Natural Science Foundation of China under Grant No.11171106
文摘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.
基金the National Natural Science Foundation of China under Grant No.10671108
文摘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.
基金National Natural Science Foundation of"China(10271110,60021201)the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE,China
文摘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.
基金National Natural Science Foundation of China ( No. 60804052 )Chen Guang Project from Shanghai Municipal Education Commission and Shanghai Education Development Foundation,China ( No. 09CG39 )Project of Shanghai Municipal Education Commission,China ( No. 12YZ020)
文摘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.
基金the National 973 Fundamental Research Project of Chinathe National Natural Sciences Foundation of China!19701028
文摘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.
基金This work was supported by the National Natural Science Foundation of China(Nos.11071142,11201259)the Natural Science Foundation of Shan Dong Province(No.ZR2010AM034)+1 种基金the Doctoral Fund of the Ministry of Education(No.20123705120001)We thank the two anonymous reviewers for their helpful and detailed comments on an earlier version of our paper.
文摘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.
基金The first author was supported by the National Natural Science Foundation of China(No.11671368)Natural Science Foundation of Henan Province(No.15IRTSTHN006)+1 种基金Tian was also supported by Natural Science Foundation of Jiangsu Province(No.BK20130169)the National Natural Science Foundation of China(No.61573362).
文摘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.