On-line scheduling to minimize average completion time revisited

We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.     

Improved algorithm for a generalized on-line scheduling problem on identical machines

This paper considers the problem of on-line scheduling a list of independent jobs in which each job has an arbitrary release time on m parallel identical machines. In this problem, jobs arrive in form of order before its release time and decisions have to be made whenever an order is placed and the orders arrive according to any sequence. A heuristic algorithm, NMLS, better than MLS is given for any m ? 2. The competitive ratio is improved from 2.93920 to 2.78436.     

On-line scheduling of unit time jobs with rejection: minimizing the total completion time

We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs.We give an on-line algorithm for this problem with competitive ratio . Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784.     

On-line supply chain scheduling problems with preemption

We consider supply chain scheduling problems where customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information on the number, release and processing times of future jobs; the processing time of a job becomes known when the job is released. Preemption is allowed. To reduce the total costs, processed jobs are grouped into batches, which are delivered to customers as single shipments; we assume that the cost of delivering a batch does not depend on the number of jobs in the batch. The objective is to minimize the total cost, which is the sum of the total flow time and the total delivery cost. For the single-customer problem, we present an on-line two-competitive algorithm, and show that no other on-line algorithm can have a better competitive ratio. We also consider an extension of the algorithm for the case of m customers, and show that its competitive ratio is not greater than 2m if the delivery costs to different customers are equal.     

On-line scheduling of small open shops

We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive.     

Approximation algorithm for the on-line multi-customer two-level supply chain scheduling problem

A manufacturer has to process jobs released on-line and deliver them to customers. Preemption is allowed. Jobs are grouped into batches for delivery. The sum of the total flow time and the total delivery cost is minimized. Deliveries to different customers cannot be combined. We present an on-line algorithm with the competitive ratio bounded by 3+α$3+\alpha$, where α$\alpha$ is the ratio of the largest processing time to the smallest processing time.     

An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines

We consider the problem of on-line scheduling a set of n jobs on two parallel batch processing machines. The objective is to minimize the makespan. We provide an algorithm for the problem that is better than one given in the literature, improving the competitive ratio from to .     

On the on-line rent-or-buy problem in probabilistic environments

Fujiwara and Iwama [In: The 13th Annual International Symposium on Algorithms and Computation, pp. 476–488 (2002)] first integrated probability distribution into the classical competitive analysis to study the rental problem. They assumed that the future inputs are drawn from an exponential distribution, and obtained the optimal competitive strategy and the competitive ratio by the derivative method. In this paper, we introduce the interest rate and tax rate into the continuous model of Fujiwra and Iwama [In: The 13th Annual International Symposium on Algorithms and Computation, pp. 476–488 (2002)]. Moreover, we use the forward difference method in different probabilistic environments to consider discrete leasing models both with and without the interest rate. We not only give the optimal competitive strategies and their competitive ratios in theory, but also give numerical results. We find that with the introduction of the interest rate and tax rate, the uncertainty involved in the process of decision making will diminish and the optimal purchasing date will be put off.     

Open shop scheduling problem to minimize makespan with release dates

The scheduling problem of open shop to minimize makespan with release dates is investigated in this paper. Unlike the usual researches to confirm the conjecture that the tight worst-case performance ratio of the Dense Schedule (DS) is 2 − 1/m, where m is the number of machines, the asymptotic optimality of the DS is proven when the problem scale tends to infinity. Furthermore, an on-line heuristic based on DS, Dynamic Shortest Processing Time-Dense Schedule, is presented to deal with the off-line and on-line versions of this problem. At the end of the paper, an asymptotically optimal lower bound is provided and the results of numerical experiments show the effectiveness of the heuristic.     

Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs

We study the on-line version of the maximum independent set problem, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds.     

A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags

We consider the one-machine scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. We describe a branch and bound algorithm, based on the input and output of a clique and the relevant propositions, for finding the optimal waiting times. The computational experiments give promising results, showing whether a given instance is feasible or infeasible. With the proposed branch and bound algorithm we can either find an optimal schedule or establish the infeasibility within an acceptable run time.     

Extension of algorithm list scheduling for a semi-online scheduling problem

A general algorithm, called ALG, for online and semi-online scheduling problem Pm||C _max 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.     

Note on Shim and Kim’s lower bounds for scheduling on identical parallel machines to minimize total tardiness

This note introduces a new lower bound for the problem of scheduling on parallel identical machines to minimize total tardiness that is based on the concepts used in the two lower bounds developed by Shim and Kim [Shim, S.O., Kim, Y.D., 2007. Scheduling on parallel identical machines to minimize total tardiness. European Journal of Operational Research 177, 135–146]. The note shows that the new lower bound dominates the three lower bounds used in Shim and Kim’s branch-and-bound algorithm and can be used in place of these lower bounds to lower the enumeration required.     

Competitive analysis of preemptive single-machine scheduling

We give an online algorithm for minimizing the total weighted completion time on a single machine where preemption of jobs is allowed and prove that its competitive ratio is at most 1.57.     

Online scheduling with general machine cost functions

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently online scheduling problems have been investigated with the modification that initially the algorithm possesses no machines, but that at any point additional machines may be purchased. In all of these models the assumption has been made that each machine has unit cost. In this paper we consider the problem with general machine cost functions. Furthermore we also consider a more general version of the problem where the available machines have speed, the algorithm may purchase machines with speed 1 and machines with speed s. We define and analyze some algorithms for the solution of these problems and their special cases. Moreover we prove some lower bounds on the possible competitive ratios.     

Online scheduling with machine cost and rejection

In this paper we define and investigate a new scheduling model. In this new model the number of machines is not fixed; the algorithm has to purchase the used machines, moreover the jobs can be rejected. We show that the simple combinations of the algorithms used in the area of scheduling with rejections and the area of scheduling with machine cost are not constant competitive. We present a 2.618-competitive algorithm called OPTCOPY.     

An improved lower bound for a bi-criteria scheduling problem

For the bi-criteria scheduling problem of minimizing the sum of completion times and the sum of weighted completion times, min-sum of weighted completion times, we prove that there exists no constant β>1 such that (1+1/γ,β)-approximate schedules can be found for any γ>0. This result confirms a recently published conjecture.