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.     

Parallel dedicated machines scheduling with chain precedence constraints

A set of n nonpreemptive tasks are to be scheduled on m parallel dedicated machines with a regular criterion. Chain precedence constraints among the tasks, deterministic processing times and processing machine of each task are given.     

An improved monotone algorithm for scheduling related machines with precedence constraints

We answer an open question posed by Krumke et al. (2008) [6] by showing how to turn the algorithm of Chekuri and Bender for scheduling related machines with precedence constraints into an O(logm)-approximation algorithm that is monotone in expectation. This significantly improves on the previously best known monotone approximation algorithms for this problem, from Krumke et al. [6] and Thielen and Krumke (2008) [8], which have an approximation guarantee of O(m^2/3).     

A monotone approximation algorithm for scheduling with precedence constraints

We provide a monotone O(m^2/3)-approximation algorithm for scheduling related machines with precedence constraints.     

Scheduling jobs with time-resource tradeoff via nonlinear programming

We consider a scheduling problem where the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The objective is to find a resource allocation and a schedule that minimizes the makespan. We explicitly allow for succinctly encodable time-resource tradeoff functions, which calls for mathematical programming techniques other than those that have been used before. Utilizing a (nonlinear) integer mathematical program, we obtain the first polynomial time approximation algorithm for the scheduling problem, with performance bound (3+ε) for any ε>0. Our approach relies on a fully polynomial time approximation scheme to solve the nonlinear mathematical programming relaxation. We also derive lower bounds for the approximation.     

On the complexity of scheduling unit-time jobs with OR-precedence constraints

We present various complexity results for scheduling unit-time jobs subject to OR-precedence constraints. We prove that minimizing the total weighted completion time is strongly NP-hard, even on a single machine. In contrast, we give a polynomial-time algorithm for minimizing the makespan and the total completion time on identical parallel machines.     

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.     

Complexity of single machine scheduling subject to nonnegative inventory constraints

This paper focuses on single machine scheduling subject to inventory constraints. Jobs either add items to an inventory or remove items from that inventory. Jobs that have to remove items cannot be processed if the required number of items is not available. We consider scheduling problems on a single machine with the minimization of the total weighted completion time, the maximum lateness, and the number of tardy jobs, respectively, as objective and determine their computational complexity. Since the general versions of our problems turn out to be strongly NP-hard, we consider special cases by assuming that different jobs have certain parameter values in common. We determine the computational complexity for all special cases when the objective is either to minimize total completion time or to minimize maximum lateness and for several special cases when the objective is either to minimize total weighted completion time or to minimize the number of tardy jobs.     

Multiprocessor scheduling under precedence constraints: Polyhedral results

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented.     

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.     

Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates

We present a $(2+2ln2+\epsilon )$-approximation algorithm for the classical nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on identical parallel machines subject to release dates and precedence constraints, improving upon the previously best known 4-approximation algorithm from 1998. The result carries over to the more general problem with precedence delays and generalizes a recent result by Li (2017) for the problem without release dates or delays.     

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.     

Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay

We consider the makespan minimization for a unit execution time task sequencing problem with a bipartite precedence delays graph and a positive precedence delay d. We prove that the associated decision problem is strongly NP-complete and we provide a non-trivial polynomial sub-case. We also give an approximation algorithm with ratio .     

New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints

We propose a new formulation for the asymmetric traveling salesman problem, with and without precedence relationships, which employs a polynomial number of subtour elimination constraints that imply an exponential subset of certain relaxed Dantzig-Fulkerson-Johnson subtour constraints. Promising computational results are presented, particularly in the presence of precedence constraints.     

Time complexity of single machine scheduling with stochastic precedence constraints

This paper deals with single machine scheduling problems with stochastic precedence relations (so calledGERT networks). Until now most investigations on such problems, dealt with algorithms running in polynomial time. On the other hand, for scheduling problems with deterministic precedence relations exist a lot of results about time complexity. Therefore, the object of this paper is to consider time complexity of scheduling problems with stochastic precedence constraints and to describe the boundary between theNP-hard problems and those which can be solved in polynomial time.     

Combined vehicle routing and scheduling with temporal precedence and synchronization constraints

We present a mathematical programming model for the combined vehicle routing and scheduling problem with time windows and additional temporal constraints. The temporal constraints allow for imposing pairwise synchronization and pairwise temporal precedence between customer visits, independently of the vehicles. We describe some real world problems where in the literature the temporal constraints are usually remarkably simplified in the solution process, even though these constraints may significantly improve the solution quality and/or usefulness. We also propose an optimization based heuristic to solve real size instances. The results of numerical experiments substantiate the importance of the temporal constraints in the solution approach. We also make a computational study by comparing a direct use of a commercial solver against the proposed heuristic, where the latter approach can find high quality solutions within specific time limits.     

Scheduling deteriorating jobs subject to job or machine availability constraints

We consider two problems of scheduling a set of independent, non-preemptable and proportionally deteriorating jobs on a single machine. In the first problem, the machine is not continuously available for processing but the number of non-availability periods, the start time and end time of each period are known in advance. In the second problem, the machine is available all the time but for each job a ready time and a deadline are defined. In both problems the criterion of schedule optimality is the maximum completion time. We show that the decision version of the first (the second) problem is NP-complete in the ordinary or in the strong sense, depending on the number of non-availability periods (the number of ready times and deadlines).