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.     

Online cardinality constrained scheduling

In online load balancing problems, jobs arrive over a list. Upon arrival of a job, the algorithm is required to assign it immediately and irrevocably to a machine. We consider such a makespan minimization problem with an additional cardinality constraint, i.e., at most k jobs may be assigned to each machine, where k is a parameter of the problem. We present both upper and lower bounds on the competitive ratio of online algorithms for this problem with identical machines.     

Online time-constrained scheduling in linear and ring networks

We consider the problem of scheduling a sequence of packets over a linear network, where every packet has a source and a target, as well as a release time and a deadline by which it must arrive at its target. The model we consider is bufferless, where packets are not allowed to be buffered in nodes along their paths other than at their source. This model applies to optical networks where opto-electronic conversion is costly, and packets mostly travel through bufferless hops. The offline version of this problem was previously studied in M. Adler et al. (2002) [3]. In this paper we study the online version of the problem, where we are required to schedule the packets without knowledge of future packet arrivals. We use competitive analysis to evaluate the performance of our algorithms. We present the first online algorithms for several versions of the problem. For the problem of throughput maximization, where all packets have uniform weights, we give an algorithm with a logarithmic competitive ratio, and present some lower bounds. For other weight functions, we show algorithms that achieve optimal competitive ratios.     

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.     

An improved algorithm for online machine minimization

The online machine minimization problem seeks to design a preemptive scheduling algorithm on multiple machines — each job $j$ arrives at its release time $r_j$, has to be processed for $p_j$ time units, and must be completed by its deadline $d_j$. The goal is to minimize the number of machines the algorithm uses. We improve the $O(logm)$-competitive algorithm by Chen, Megow and Schewior (SODA 2016) and provide an $O\left(\frac{logm}{loglogm}\right)$-competitive algorithm.     

Single-machine and two-machine flowshop scheduling with general learning functions

We show that the O(n log n) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment.     

Online scheduling of parallel jobs on two machines is 2-competitive

We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, we show that 2 is a tight lower bound on the competitive ratio. For the problem with m machines, we derive lower bounds using an ILP formulation.     

Parallel machine scheduling with nested job assignment restrictions

We derive a polynomial time approximation scheme for a special case of makespan minimization on unrelated machines.     

Bounded delay packet scheduling in a bounded buffer

We study buffer management in QoS-enabled network switches in the bounded delay model where each packet has a weight and a deadline. We consider the more realistic situation where the switch has a finite buffer size. A 9.82-competitive algorithm is known for the case of multiple buffers. Recently, for the single buffer case, a 3-competitive deterministic algorithm and a 2.618-competitive randomized algorithm were found. We give a simple deterministic 2-competitive algorithm for the single buffer case.     

On the machine scheduling problem with job delivery coordination

This paper examines two scheduling problems with job delivery coordination, in which each job demands different amount of storage space during transportation. For the first problem, in which jobs are processed on a single machine and delivered by one vehicle to a customer, we present a best possible approximation algorithm with a worst-case ratio arbitrarily close to 3/2. For the second problem, which differs from the first problem in that jobs are processed by two parallel machines, we give an improved algorithm with a worst-case ratio 5/3.     

Competitive online scheduling of perfectly malleable jobs with setup times

We study how to efficiently schedule online perfectly malleable parallel jobs with arbitrary arrival times on m ? 2 processors. We take into account both the linear speedup of such jobs and their setup time, i.e., the time to create, dispatch, and destroy multiple processes. Specifically, we define the execution time of a job with length p_j running on k_j processors to be p_j/k_j + (k_j − 1)c, where c > 0 is a constant setup time associated with each processor that is used to parallelize the computation. This formulation accurately models data parallelism in scientific computations and realistically asserts a relationship between job length and the maximum useful degree of parallelism. When the goal is to minimize makespan, we show that the online algorithm that simply assigns k_j so that the execution time of each job is minimized and starts jobs as early as possible has competitive ratio 4(m − 1)/m for even m ? 2 and 4m/(m + 1) for odd m ? 3. This algorithm is much simpler than previous offline algorithms for scheduling malleable jobs that require more than a constant number of passes through the job list.     

Online competitive algorithms for maximizing weighted throughput of unit jobs

We study an online unit-job scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unit-job scheduling, as well as some lower bounds on the competitive ratios.We first give a randomized algorithm RMix with competitive ratio of e/(e−1)≈1.582. This is the first algorithm for this problem with competitive ratio smaller than 2.Then we consider s-bounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm Edf_α, whose competitive ratio on s-bounded instances is 2−2/s+o(1/s). For 3-bounded instances its ratio is ≈1.618, matching the known lower bound.In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform instances, if the span s is unbounded. For s=2, our proof gives a lower bound of . Also, in the 2-uniform case, we prove a lower bound of for deterministic memoryless algorithms, matching a known upper bound.Finally, we investigate the multiprocessor case and give a -competitive algorithm for m processors. We also show improved lower bounds for the general and s-uniform cases.     

Optimal scheduling in film production to minimize talent hold cost

The problem of minimizing the cost due to talent hold days in the production of a feature film is considered. A combinatorial model is developed for the sequencing of shooting days in a film shoot. The problem is shown to be strongly NP-hard. A branch-and-bound solution algorithm and a heuristic solution method for large instances of the problem (15 shooting days or more) are developed and implemented on a computer. A number of randomly generated problem instances are solved to study the power and speed of the algorithms. The computational results reveal that the heuristic solution method is effective and efficient in obtaining near-optimal solutions.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG-0036424. The authors are thankful to two anonymous referees for their helpful comments on an earlier version of this paper.     

Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.