Two machine preemptive scheduling problem with release dates,equal processing times and precedence constraints

We consider a scheduling problem with two identical parallel machines and n jobs. For each job we are given its release date when job becomes available for processing. All jobs have equal processing times. Preemptions are allowed. There are precedence constraints between jobs which are given by a (di)graph consisting of a set of outtrees and a number of isolated vertices. The objective is to find a schedule minimizing mean flow time. We suggest an O(n²) algorithm to solve this problem.The suggested algorithm also can be used to solve the related two-machine open shop problem with integer release dates, unit processing times and analogous precedence constraints.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

Parallel machine scheduling with a convex resource consumption function

We consider some problems of scheduling jobs on identical parallel machines where job-processing times are controllable through the allocation of a nonrenewable common limited resource. The objective is to assign the jobs to the machines, to sequence the jobs on each machine and to allocate the resource so that the makespan or the sum of completion times is minimized. The optimization is done for both preemptive and nonpreemptive jobs. For the makespan problem with nonpreemptive jobs we apply the equivalent load method in order to allocate the resources, and thereby reduce the problem to a combinatorial one. The reduced problem is shown to be NP-hard. If preemptive jobs are allowed, the makespan problem is shown to be solvable in O(n²) time. Some special cases of this problem with precedence constraints are presented and the problem of minimizing the sum of completion times is shown to be solvable in O(n log n) time.     

Precedence constrained parallel-machine scheduling of position-dependent jobs

We consider parallel-machine job scheduling problems with precedence constraints. Job processing times are variable and depend on positions of jobs in a schedule. The objective is to minimize the maximum completion time or the total weighted completion time. We specify certain conditions under which the problem can be solved by scheduling algorithms applied earlier for fixed job processing times.     

Scheduling linearly shortening jobs under precedence constraints

We consider the problem of scheduling a set of dependent jobs on a single machine with the maximum completion time criterion. The processing time of each job is variable and decreases linearly with respect to the starting time of the job. Applying a uniform approach based on the calculation of ratios of expressions that describe total processing times of chains of jobs, we show basic properties of the problem. On the basis of these properties, we prove that if precedence constraints among jobs are in the form of a set of chains, a tree, a forest or a series–parallel digraph, the problem can be solved in O(n log n) time, where n denotes the number of the jobs.     

On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times

We consider the single machine, serial batching, total completion time scheduling problem with precedence constraints, release dates and identical processing times in this paper. The complexity of this problem is reported as open in the literature. We provide an O(n⁵) time algorithm to solve this problem.     

Parallel machine scheduling with machine availability and eligibility constraints

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.     

Minimizing a Quadratic Cost Function of Waiting Times in Single-Machine Scheduling

This paper deals with scheduling n jobs on a single machine in order to minimize the weighted sum of squared waiting times of the jobs. We present a powerful decomposition mechanism, based on a precedence relation concept, that easily handles problems of the size n = 50 and 100 where the processing times and penalties are independently drawn from a uniform distribution. This mechanism is incorporated along with new branching rules in a branch-and-bound scheme that efficiently handles tough problems of the size 20 and 50.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Preemptive Hybrid Flowshop Scheduling problem of interval orders

The Preemptive Hybrid (multi-processor) Flowshop Scheduling (PHFS) problem consists in preemptively scheduling n jobs in a flowshop subject to precedence constraints with the objective of minimizing the makespan. A special case of the general precedence constraints problems is NP-hard in the strong sense, Hoogeveen et al. [J.A. Hoogeveen, J.K. Lenstra, B. Veltman, European Journal of Operational Research 89 (1996) 172]. In this paper a class of precedence constraints is proposed for which the problem is polynomially solvable. The reported results demonstrate the feasibility and reliability of the proposed approach. This should open future prospects for developing approximation algorithms for any class of precedence constraints.     

An algorithm for single machine sequencing with release dates to minimize total weighted completion time

Each of n jobs is to be processed without interruption on a single machine which can handle only one job at a time. Each job becomes available for processing at its release date, requires a processing time and has a positive weight. Given a processing order of the jobs, the earliest completion time for each job can be computed. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times. In this paper a branch and bound algorithm for the problem is derived. Firstly a heuristic is presented which is used in calculating the lower bound. Then the lower bound is obtained by performing a Lagrangean relaxation of the release date constraints; the Lagrange multipliers are chosen so that the sequence generated by the heuristic is an optimum solution of the relaxed problem thus yielding a lower bound. A method to increase the lower bound by deriving improved constraints to replace the original release date constraints is given. The algorithm, which includes several dominance rules, is tested on problems with up to fifty jobs. The computational results indicate that the version of the lower bound using improved constraints is superior to the original version.     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.     

A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times

We consider the problem of scheduling n independent jobs on m unrelated parallel machines with sequence-dependent setup times and availability dates for the machines and release dates for the jobs to minimize a regular additive cost function. In this work, we develop a new branch-and-price optimization algorithm for the solution of this general class of parallel machines scheduling problems. A new column generation accelerating method, termed “primal box”, and a specific branching variable selection rule that significantly reduces the number of explored nodes are proposed. The computational results show that the approach solves problems of large size to optimality within reasonable computational time.     

Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap

Coupled tasks scheduling was originally introduced for modelling complex radar devices. It is still used for controlling such devices and applied in similar applications. This paper considers a problem of coupled tasks scheduling on one processor, under the assumptions that all processing times are equal to 1, the gap has a constant exact length and the precedence constraints are strict. Although it is proven that the problem stated above is NP-hard in the strong sense if the precedence constraints have a form of a general graph, it is possible to solve some of its relaxed versions in polynomial time. This paper contains a solution for the problem of coupled tasks scheduling with an assumption that the precedence constraints graph has a form of chains and it presents an algorithm that can solve the problem with such assumption in time O(n?log?n).     

一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究

本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界.     

Scheduling in a contaminated area: A model and polynomial algorithms

There are n jobs to be scheduled in a contaminated area. The jobs can be rescue, de-activation or cleaning works to be executed by a single worker in an area contaminated with radio-active or chemical materials. Precedence relations can be given on the set of jobs. An execution of each job can be preempted. However, the length of the minimal uninterrupted work period is given and it is the same for all jobs. Each work period for a job should be accompanied by a rest period whose length depends on the start time of the work period and its length. We focus on a short term planning problem. We show that this problem can be modelled by a scheduling problem with start time dependent job processing times. The dependency functions are exponentially decreasing ones. We also construct two polynomial time algorithms for the both cases—with and without precedence constraints.     

A bicriteria flowshop scheduling with a learning effect

In many situations, a worker’s ability improves as a result of repeating the same or similar tasks; this phenomenon is known as the learning effect. In this paper the learning effect is considered in a two-machine flowshop. The objective is to find a sequence that minimizes a weighted sum of total completion time and makespan. Total completion time and makespan are widely used performance measures in scheduling literature. To solve this scheduling problem, an integer programming model with n² + 6n variables and 7n constraints where n is the number of jobs is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 30 jobs can be solved. A heuristic algorithm and a tabu search based heuristic algorithm are presented to solve large size problems. Experimental results show that the proposed heuristic methods can solve this problem with up to 300 jobs rapidly. According to the best of our knowledge, no work exists on the bicriteria flowshop with a learning effect.     

Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.     

Batch delivery scheduling with batch delivery cost on a single machine

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on a single machine. The jobs are delivered in batches and the delivery date of a batch equals the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total weighted flow time and delivery cost. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B ? U for a variable U ? 2 or B ? U for any constant U ? 2. For the case of B ? U, we present a dynamic programming algorithm that runs in pseudo-polynomial time for any constant U ? 2. Furthermore, optimal algorithms are provided for two special cases: (i) jobs have a linear precedence constraint, and (ii) jobs satisfy the agreeable ratio assumption, which is valid, for example, when all the weights or all the processing times are equal.     

Scheduling jobs with chain precedence constraints and deteriorating jobs

In this paper we consider a single machine scheduling problem with deteriorating jobs. By deteriorating jobs, we mean that the processing time of a job is a simple linear function of its execution starting time. For the jobs with chain precedence constraints, we prove that the weighted sum of squared completion times minimization problem with strong chains and weak chains can be solved in polynomial time, respectively.