A polynomially solvable case of the three machine johnson problem

Under study is the classical NP-hard problem with three machines: N tasks must be fulfilled at three machines in minimum time. The processing time is given of each task at each machine. The processing sequences of all tasks are identical. It is impossible to process two tasks at one machine at the same time. We address the properties of this problem, find a new polynomially solvable case, and discuss a corresponding algorithm.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

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.     

δ-Uniform BSS Machines

Aδ-uniform BSS machine is a standard BSS machine which does not rely on exact equality tests. We prove that, for any real closed archimedean fieldR, a set isδ-uniformly semi-decidable iff it is open and semi-decidable by a BSS machine which is locally time bounded; we also prove that the local time bound condition is nontrivial. This entails a number of results about BSS machines, in particular the existence of decidable sets whose interior (closure) is not even semi-decidable without adding constants. Finally, we show that the sets semi-decidable by Turing machines are the sets semi-decidable byδ-uniform machines with coefficients inQorT, the field of Turing computable numbers.     

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.     

Scheduling unit — time tasks on flow — shops under resource constraints

We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is proved that when the number of machines is arbitrary, the problem of minimizing schedule length is NP-hard, even when only one unit of the additional resource is available in the system. On the other hand, when the number of machines is fixed, then the problem is solvable in polynomial time, even for an arbitrary number of resource units available. For the two machine case anO(n log ₂ ² n) algorithm minimizing maximum lateness is also given. The presented results are also of importance in some message transmission systems.     

A linear time approximation algorithm for movement minimization in conveyor flow shop processing

We consider the movement minimization problem in a conveyor flow shop processing controlled by one worker for all machines. A machine can only execute tasks if the worker is present. Each machine can serve as a buffer. The worker has to cover a certain distance to move from one machine to the other. The distance between two machines P_p and P_q is |p−q|. The objective is to minimize the total distance the worker has to cover for the processing of all jobs. We introduce a linear time approximation algorithm for the conveyor flow shop problem with performance 3. Such minimization problems usually appear in conveyor controlled manufacturing systems.     

Optimal on-line flow time with resource augmentation

We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules jobs on a single machine is compared to a more powerful on-line algorithm that has ? machines. We design an algorithm of competitive ratio , where Δ is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant ?. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only Δ and n are known. This gives a trade-off between the resource augmentation and the competitive ratio.We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has ?m machines. We give a lower bound for this case. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines, and scheduling so as to minimize the total completion time.     

Selfish load balancing for jobs with favorite machines

This paper studies the load balancing game for the favorite machine model, where each job has a certain set of favorite machines with the shortest processing time for the job. We obtain tight bounds on the Strong Price of Anarchy (strong PoA) for the general favorite machine model and a special case of the model. Our results generalize the well-known bounds on the strong PoA for the unrelated machine and identical machine models.     

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.     

Scheduling tasks on a flexible manufacturing machine to minimize tool change delays

This paper considers the problem of scheduling a given set of precedence constraint tasks on a flexible machine equipped with a tool magazine where each task requires exactly one of the tools during its execution. Changing from one tool to another requires a certain amount of time that depends on the pair of tools being exchanged. We present a new algorithmic approach for general task precedence relations when it is desired to sequence the tasks in such a way that the total time required for tool changes is minimized. The proposed algorithm is of polynomial time complexity in case of task precedences of limited width w, i.e. for precedence relations where each subset of independent tasks has not more than w elements. Since the task precedences width w could be arbitrary, we describe two heuristic algorithms and empirically evaluate their effectiveness in finding schedules with minimum total time required for tool changes.     

The efficiency of bi-directionally patrolled machines when repairs are not always successful

This paper solves the problem of calculating the effective rate of production of a set of N machines, under the care of one operative, whose method of working is to patrol the machines, first in one direction until all the machines have been inspected and then in the opposite direction, and so on. The time taken to walk from one machine to the next, and inspect and service that machine is assumed to be a constant and is called the walking time. If a machine is stopped when the operative reaches it he spends an additional constant repair time putting it in order before proceeding to the next machine. The problem arises in the practical context of a textile winding process in which the operative is a robot which is not always successful in its attempt to carry out a repair. The numerical results are of value in monitoring this process.     

Production planning problem with sequence dependent setups as a bilevel programming problem

Each of n products is to be processed on two machines in order to satisfy known demands in each of T periods. Only one product can be processed on each machine at any given time. Each switch from one item to another requires sequence dependent setup time. The objective is to minimize the total setup time and the sum of the costs of production, storage and setup. We consider the problem as a bilevel mixed 0–1 integer programming problem. The objective of the leader is to assign the products to the machines in order to minimize the total sequence dependent setup time, while the objective of the follower is to minimize the production, storage and setup cost of the machine. We develop a heuristics based on tabu search for solving the problem. At the end, some computational results are presented.     

Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems

This paper presents an exact algorithm for the identical parallel machine scheduling problem over a formulation where each variable is indexed by a pair of jobs and a completion time. We show that such a formulation can be handled, in spite of its huge number of variables, through a branch cut and price algorithm enhanced by a number of practical techniques, including a dynamic programming procedure to fix variables by Lagrangean bounds and dual stabilization. The resulting method permits the solution of many instances of the P||∑w _j T _j problem with up to 100 jobs, and having 2 or 4 machines. This is the first time that medium-sized instances of the P||∑w _j T _j have been solved to optimality.     

Bicriteria scheduling for contiguous and non contiguous parallel tasks

We study the problem of scheduling on k identical machines a set of parallel tasks with release dates and deadlines in order to maximize simultaneously two criteria, namely the Size (number of scheduled tasks) and the Weight (sum of the weights of scheduled tasks). If no task requires more than half of the machines, we construct schedules that are simultaneously approximations for the Size and the Weight by combining two approximate schedules, one for each parameter. We obtain existence results and polynomial time bicriteria approximation algorithms in contiguous and non contiguous models.     

New trends in machine scheduling

This review is concerned with new directions in deterministic machine scheduling theory. We study: resource constrained scheduling, scheduling tasks that require more than one machine at a time, scheduling with nonlinear speed-resource alloted functions, and scheduling in flexible manufacturing systems. The two features that distinguish the above problems are the use of resources in addition to the machines and new models for the processing of tasks. The study of these models was primarily motivated by their practical importance. In each case, we overview the existing results and present solution strategies for particularly chosen problems.     

Maximizing the minimum completion time on parallel machines

We propose an exact branch-and-bound algorithm for the problem of maximizing the minimum machine completion time on identical parallel machines. The proposed algorithm is based on tight lower and upper bounds as well as an effective symmetry-breaking branching strategy. Computational results performed on a large set of randomly generated instances attest to the efficacy of the proposed algorithm.      

The efficiency of unidirectionally patrolled machines

This paper solves the problem of determining the efficiency of N (not identical) machines which are unidirectionally patrolled by one operative. Generally the machines will be equally spaced in a circular configuration so that the time to walk from one machine to the next will be a constant. However, the case of unequal spacing is just as easy to handle. It is assumed that breakdowns of machine j occur at random at average rate γ_j in running time, and that the time to repair this machine is a constant, c_j. This situation could arise from a mix of new and old machines or, in a textile context, in a situation where different types of yarn are being processed on different machines.     

New steps in the amazing world of sequences and schedules

In this paper we consider classical shop problems:n jobs have to be processed onm machines. The processing timep _i,j of jobi on machinej is given for all operations (i, j). Each machine can process at most one job at a time and each job can be processed at most on one machine at a given time. The machine orders are fixed (job-shop) or arbitrary (open-shop). We have to determine a feasible combination of machine and job orders, a so-called sequence, which minimizes the makespan. We introduce a partial order on the set of sequences with the property that there exists at least one optimal sequence in the set of minimal elements of this partial order independent of the given processing times. The set of minimal elements (set of irreducible sequences) can be in detail described in the case of the two machine open-shop problem. The cardinality is calculated. We will show which sequences are generated by the well-known polynomial algorithms for the construction of optimal schedules. Furthermore, we investigate the problemO∥C _max on an operation set with spanning tree structure. Supported by Deutsche Forschungsgemeinschaft, Project ScheMA