A new algorithm for online uniform-machine scheduling to minimize the makespan

We consider the online scheduling problem with m−1, m?2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1?s?2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91-103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422]. It has a worst-case bound of 2.8795 for a big m and s=2. In this note we present a 2.45-competitive algorithm for m?4 and any s, 1?s?2.     

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.     

Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time

We consider online scheduling on m unbounded parallel-batch machines to minimize maximum flow-time of the jobs. We show that no online algorithm can have a competitive ratio less than 1+αm, where αm is the positive root of α²+(m+1)α−1=0, and this lower bound is still valid even when all jobs have the same processing times. Then we provide an online algorithm of competitive ratio 1+1/m. When the jobs have the same processing times, we present a best possible online algorithm of competitive ratio 1+αm.     

Online scheduling of two job types on a set of multipurpose machines with unit processing times

We study a problem of scheduling a set of n jobs with unit processing times on a set of m multipurpose machines in which the objective is to minimize the makespan. It is assumed that there are two different job types, where each job type can be processed on a unique subset of machines. We provide an optimal offline algorithm to solve the problem in constant time and an online algorithm with a competitive ratio that equals the lower bound. We show that the worst competitive ratio is obtained for an inclusive job-machine structure in which the first job type can be processed on any of the m machines while the second job type can be processed only on a subset of m/2 machines. Moreover, we show that our online algorithm is 1-competitive if the machines are not flexible, i.e., each machine can process only a single job type.     

Online batch scheduling on parallel machines with delivery times

We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4, we present an online algorithm with a competitive ratio of 1.5+o(1).     

Optimal online algorithm for scheduling on two identical machines with machine availability constraints

This paper considers the online scheduling on two identical machines with machine availability constraints for minimizing makespan. We assume that machine M_j is unavailable during period from s_j to t_j (0?s_j<t_j), j=1,2, and the unavailable periods of two machines do not overlap. We show the competitive ratio of List Scheduling is 3. We further give an optimal algorithm with a competitive ratio 5/2.     

On-line scheduling of parallel machines to minimize total completion times

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$m$ identical parallel machines. We show that this algorithm is 2-competitive and the bound is tight.     

On-line scheduling with extendable working time on a small number of machines

Speranza and Tuza [Ann. Oper. Res. 86 (1999) 494-506] studied the on-line problem of scheduling jobs on m identical machines with extendable working time. In this problem, each machine is assumed to have an identical regular working time, which can be extended if necessary. The working time of a machine is the larger one between its regular working time and the total processing time of jobs assigned to it. The objective is to minimize the total working time of machines. They presented an on-line algorithm H_x, with a competitive ratio at most 1.228 for any number of machines by choosing an appropriate parameter x. In this paper we consider a small number of machines. The best choices of x are given for m=2,3,4 and the tight bounds, 7/6, 11/9 and 19/16, respectively, are proved. Among them, the algorithm for m=2 is best possible. We then derive a new algorithm for m=3 with a competitive ratio 7/6.     

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.     

Online interval scheduling on a single machine with finite lookahead

We study an online weighted interval scheduling problem on a single machine, where all intervals have unit length and the objective is to maximize the total weight of all completed intervals. We investigate how the function of finite lookahead improves the competitivities of deterministic online heuristics, under both preemptive and non-preemptive models. The lookahead model studied in this paper is that an online heuristic is said to have a lookahead ability of LD if at any time point it is able to foresee all the intervals to be released within the next LD   units of time. We investigate both competitive online heuristics and lower bounds on the competitive ratio, with lookahead 0≤LD≤1$0\le \mathit{LD}\le 1$ under the preemptive model, and lookahead 0≤LD≤2$0\le \mathit{LD}\le 2$ under the non-preemptive model. A method to transform a preemptive lookahead online algorithm to a non-preemptive online algorithm with enhanced lookahead ability is also given. Computational tests are performed to compare the practical competitivities of the online heuristics with different lookahead abilities.     

Single-machine scheduling with periodic maintenance to minimize makespan

We consider a single-machine scheduling problem with periodic maintenance activities. Although the scheduling problem with maintenance has attracted researchers’ attention, most of past studies considered only one maintenance period. In this research several maintenance periods are considered where each maintenance activity is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the makespan, subject to periodic maintenance and nonresumable jobs. We first prove that the worst-case ratio of the classical LPT   algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case ratio less than 2 unless P=NP$P=\text{<italic>NP</italic>}$, which implies that the LPT algorithm is the best possible.     

Online scheduling on semi-related machines

We study the problem of minimizing the makespan on related machines in the following setting: jobs arrive over time, and the machines may become available or unavailable. In either case, advance warning is given, i.e., the next point of time where a job is released or a machine changes state is revealed a little time ahead. We present an optimal online algorithm for this problem.     

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.