Resource leveling in a machine environment

We address resource leveling problems in a machine environment. Given a set of m machines, one or more renewable resources, and a set of n tasks, each assigned to exactly one of the machines. Each task has a processing time, an earliest start time, a deadline, and resource requirements. There are no precedence relations between the tasks. The tasks have to be sequenced on the machines while minimizing a function of the level of resource utilization from each resource over time. We provide various complexity results including a polynomial time algorithm for a one machine special case. We also propose an exact method using various techniques to find optimal or close-to-optimal solutions. The computational experiments show that our exact method significantly outperforms heuristics and a commercial MIP solver.     

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.     

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.     

Single-job lot streaming in m − 1 two-stage hybrid flowshops

This paper studies the single-job lot streaming problem in a two-stage hybrid flowshop that has m identical machines at the first stage and one machine at the second stage, to minimise the makespan. A setup time is considered before processing each sublot on a machine. For the problem with the number of sublots given, we prove that it is optimal to use a rotation method for allocating and sequencing the sublots on the machines. With such allocation and sequencing, the sublot sizes are then optimised using linear programming. We then consider the problem with equal sublot sizes and develop an efficient solution to determining the optimal number of sublots. Finally optimal and heuristic solution methods for the general problem are proposed and the worst-case performance of the equal-sublot solution is analysed. Computational results are also reported demonstrating the close-to-optimal performances of the heuristic methods in different problem settings.     

Some no-wait shops scheduling problems: Complexity aspect

We investigate the computational complexity of no-wait shops scheduling problems. The problem of finding optimal finish time schedules is shown to be NP-hard for flowshops with two machine centres where each machine centre has one or more parallel machines for processing tasks. The complexity results are also reported for no-wait shops scheduling when all nonzero tasks have unit or identical processing time requirement. A polynomial time algorithm for 3-machine flowshops is proposed for optimal finish time schedules. Finding optimal finish time schedules in 2-machine jobshops in NP-hard. Also we establish NP-hard results for 3-machine jobshops for both optimal finish time and mean flow time schedules. Some results are deduced with the present work and with those reported earlier.     

Balancing Workloads and Minimizing Set-up Costs in the Parallel Processing Shop

This paper presents an optimal scheduling algorithm for minimizing set-up costs in the parallel processing shop while meeting workload balancing restrictions.There are M independent batch type jobs which have sequence dependent set-up costs and N parallel processing machines. Each of the M jobs must be processed on exactly one of the N available machines. It is desirable to minimize total changeover costs with the restriction that each machine workload assignment T _n be within P units of the average machine assignment. The paper describes a static problem in which all jobs are available at time zero. The sequence dependent change over costs are identical for each machine. An extension of the algorithm handles nonidentical processor problems.A combinatorial programming approach to the problem is used. For the special case of identical processors, the problem can be treated as a multi-salesman travelling salesman problem. A general branch and bound algorithm and numerical results are given.     

Optimal preemptive scheduling on uniform machines with discounted flowtime objectives

We consider the problem of scheduling n jobs on m parallel machines. Each job has a deterministic processing time and a weight associated with it. For uniform machines we show that discounted flowtime is minimized by serving jobs preemptively in increasing order of their remaining processing times, assigning the job with the shortest remaining processing time to the fastest available machine.     

Minimizing due date related performance measures on two batch processing machines

This paper considers a scheduling problem in a two-machine flowshop of two batch processing machines. On each batch processing machine, jobs are processed in a batch, and each batch is allowed to contain jobs up to the maximum capacity of the associated machine. The scheduling problem is analyzed with respect to three due date related objectives including maximum tardiness, number of tardy jobs and total tardiness. In the analysis, several solution properties are characterized and based upon these properties, three efficient polynomial time algorithms are developed for minimizing the due date related measures.     

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.     

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.     

Scheduling jobs with release dates,equal processing times,and inclusive processing set restrictions

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n²+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.     

An O(n) algorithm for the variable common due date,minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

We consider the ordinary NP- hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. We present an O(n²) algorithm for the problem when the machines are ordered, that is, when each job has its smaller processing time on the first (second) machine. We also discuss the applicability of the proposed algorithm to the corresponding single-objective problem in which the common due date is given.     

Pattern scheduling

A pattern is a sequence of disjoint intervals on a circle together with fixed distances between these intervals. The intervals may be interpreted as tasks of a job which is produced perio-dically on one machine. How shouldr patterns be moved relative to each other to minimize the maximum overlapping of intervals (machines needed)? An enumerative procedure for solving this problem is given.     

Due-date assignment on uniform machines

The classical weighted minsum scheduling and due-date assignment problem (with earliness, tardiness and due-date costs) was shown to be polynomially solvable on a single machine, more than two decades ago. Later, it was shown to have a polynomial time solution in the case of identical processing time jobs and parallel identical machines. We extend the latter setting to parallel uniform machines. We show that the two-machine case is solved in constant time. Furthermore, the problem remains polynomially solvable for a given (fixed) number of machines.     

Scheduling incompatible tasks on two machines

The paper studies the problem of scheduling tasks on two machines to minimize the makespan. The tasks are assigned to the machine in advance. An incompatibility relation is defined over the tasks which forbids any two incompatible tasks to be processed at the same time. The problem can serve as a mathematical model for some batching problems in which the jobs are grouped in pairs on two machines. A linear-time algorithm is presented.     

Scheduling parallel machines with inclusive processing set restrictions and job release times

We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed.     

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.     

Stochastically minimizing total flowtime in flowshops with no waiting space

The problem of scheduling n jobs in a two-machine flowshop with constant and known processing times is considered with the total flowtime performance measure. The machines are subject to random breakdowns and there is no waiting space between them. The problem is formulated and an expression for the completion time of the jobs is obtained in terms of the processing times and the breakdown elements. Provided that the counting processes associated with both machines have stationary increments property, a sequence that stochastically minimizes the performance criterion is established for the cases when only the first or the second machine suffers breakdowns.     

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.