Scheduling with multiple servers

In this paper, we consider the problem of scheduling a set of jobs on a set of identical parallel machines. Before the processing of a job can start, a setup is required which has to be performed by a given set of servers. We consider the complexity of such problems for the minimization of the makespan. For the problem with equal processing times and equal setup times we give a polynomial algorithm. For the problem with unit setup times, m machines and m − 1 servers, we give a pseudopolynomial algorithm. However, the problem with fixed number of machines and servers in the case of minimizing maximum lateness is proven to be unary NP-hard. In addition, recent algorithms for some parallel machine scheduling problems with constant precessing times are generalized to the corresponding server problems for the case of constant setup times. Moreover, we perform a worst case analysis of two list scheduling algorithms for makespan minimization.     

Pure cycles in flexible robotic cells

In this study, an m-machine flexible robotic manufacturing cell consisting of CNC machines is considered. The flexibility of the machines leads to a new class of robot move cycles called the pure cycles. We first model the problem of determining the best pure cycle in an m-machine cell as a special travelling salesman problem in which the distance matrix consists of decision variables as well as parameters. We focus on two specific cycles among the huge class of pure cycles. We prove that, in most of the regions, either one of these two cycles is optimal. For the remaining regions we derive worst case performances of these cycles. We also prove that the set of pure cycles dominates the flowshop-type robot move cycles considered in the literature. As a design problem, we consider the number of machines in a cell as a decision variable. We determine the optimal number of machines that minimizes the cycle time for given cell parameters such as the processing times, robot travel times and the loading/unloading times of the machines.     

Robotic Cells with Parallel Machines: Throughput Maximization in Constant Travel-Time Cells

We present a general analysis of the problem of sequencing operations in bufferless robotic cell flow shops with parallel machines. Our focus will be cells that produce identical parts. The objective is to find a cyclic sequence of robot moves that maximizes the steady state throughput. Parallel machines are used in the industry to increase throughput, most typically at bottleneck processes having larger processing times.Efficient use of parallel machines requires that several parts be processed in one cycle of robot movements. We analyze such cycles for constant travel-time robotic cells. The number of cycles that produce several parts is very large, so we focus on a subclass called blocked cycles. In this class, we find a dominating subclass called LCM Cycles.The results and the analysis in this paper offer practitioners (i) guidelines to determine whether parallel machines will be cost-effective for a given implementation, (ii) a simple formula for determining how many copies of each machine are required to meet a particular throughput rate, and (iii) an optimal sequence of robot moves for a cell with parallel machines under a certain common condition on the processing times.     

The complexity of mean flow time scheduling problems with release times

We study the problem of preemptive scheduling of n} jobs with given release times on m identical parallel machines. The objective is to minimize the average flow time. In this paper, show that when all jobs have equal processing times then the problem can be solved in polynomial time using linear programming. Our algorithm can also be applied to the open-shop problem with release times and unit processing times. For the general case (when processing times are arbitrary), we show that the problem is unary NP-hard. P. Baptiste and C. Dürr: Supported by the NSF/CNRS grant 17171 and ANR/Alpage. P. Brucker: Supported by INTAS Project 00-217 and by DAAD PROCOPE Project D/0427360. M. Chrobak: Supported by NSF grants CCR-0208856 and INT-0340752. S. A. Kravchenko: Supported by the Alexander von Humboldt Foundation.     

Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria

The problem of scheduling N jobs on M uniform parallel machines is studied. The objective is to minimize the mean tardiness or the weighted sum of tardiness with weights based on jobs, on periods or both. For the mean tardiness criteria in the preemptive case, this problem is NP-hard but good solutions can be calculated with a transportation problem algorithm. In the nonpreemptive case the problem is therefore NP-hard, except for the cases with equal job processing times or with job due dates equal to job processing times. No dominant heuristic is known in the general nonpreemptive case. The author has developed a heuristic to solve the nonpreemptive scheduling problem with unrelated job processing times. Initially, the algorithm calculates a basic solution. Next, it considers the interchanges of job subsets to equal processing time sum interchanging resources (i.e. a machine for a given period). This paper models the scheduling problem. It presents the heuristic and its result quality, solving 576 problems for 18 problem sizes. An application of school timetable scheduling illustrates the use of this heuristic.     

Scheduling of coupled tasks with unit processing times

The coupled tasks scheduling problem was originally introduced for modeling 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 a single processor, under the assumptions that all processing times are equal to 1, the gap has exact integer length L and the precedence constraints are strict. We prove that the general problem, when L is part of the input and the precedence constraints graph is a general graph, is NP-hard in the strong sense. We also show that the special case when L=2 and the precedence constraints graph is an in-tree or an out-tree, can be solved in O(n) time.     

Scheduling jobs with equal processing times and time windows on identical parallel machines

We present a linear programming approach to the problem of scheduling equal processing time jobs with release dates and deadlines on identical parallel machines. The known algorithm with complexity O(n ³log log n) of B. Simons schedules all the jobs while minimizing both the maximum completion time and the mean flow time. Our approach permits also to minimize the weighted sum of completion times and total tardiness in polynomial time for the problems without deadlines. The complexity status of these problems was open. Contract/grant sponsor: Alexander von Humboldt Foundation.     

Scheduling jobs with equal processing times subject to machine eligibility constraints

We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios.     

Efficient Approximation Schemes for Scheduling Problems with Release Dates and Delivery Times

We consider the problem of scheduling n independent jobs on m identical machines that operate in parallel. Each job must be processed without interruption for a given amount of time on any one of the m machines. In addition, each job has a release date, when it becomes available for processing, and, after completing its processing, requires an additional delivery time. The objective is to minimize the time by which all jobs are delivered. In the notation of Graham et al. (1979), this problem is noted P|r _j|L_max. We develop a polynomial time approximation scheme whose running time depends only linearly on n. This linear complexity bound gives a substantial improvement of the best previously known polynomial bound (Hall and Shmoys, 1989). Finally, we discuss the special case of this problem in which there is a single machine and present an improved approximation scheme.     

Scheduling in Reentrant Robotic Cells: Algorithms and Complexity

We study the scheduling of m-machine reentrant robotic cells, in which parts need to reenter machines several times before they are finished. The problem is to find the sequence of 1-unit robot move cycles and the part processing sequence which jointly minimize the cycle time or the makespan. When m = 2, we show that both the cycle time and the makespan minimization problems are polynomially solvable. When m = 3, we examine a special class of reentrant robotic cells with the cycle time objective. We show that in a three-machine loop-reentrant robotic cell, the part sequencing problem under three out of the four possible robot move cycles for producing one unit is strongly -hard. The part sequencing problem under the remaining robot move cycle can be solved easily. Finally, we prove that the general problem, without restriction to any robot move cycle, is also intractable.     

Cyclic scheduling of a robotic flexible cell with load lock and swap

In this paper, we study the problem of robotic cell scheduling with m machines with flexibility, load lock and swap assumptions. The robotic cell repetitively produces parts of identical types. We determine the cycle time of all 1-unit cycles in this type of robotic cell and present two new lower bounds for robot move cycles with load lock and swap, either there is flexibility or inflexibility. We also provide a new robot move cycle and prove that it dominates all classical robot move cycles considered in the existing literature of m-machine robotic cells.     

Parametric algorithms for 2-cyclic robot scheduling with interval processing times

Consider an m-machine production line for processing identical parts served by a mobile robot. The problem is to find the minimum cycle time for 2-cyclic schedules, that is, schedules in which exactly two parts enter and two parts leave the production line during each cycle. This work treats a special case of the 2-cyclic robot scheduling problem when the robot route is given and operation durations are chosen from prescribed intervals. A strongly polynomial algorithm of time complexity O(m ⁸log m) is proposed.     

Batching and scheduling in a multi-machine flow shop

We study the problem of batching and scheduling n jobs in a flow shop comprising m, m≥2, machines. Each job has to be processed on machines 1,…,m in this order. Batches are formed on each machine. A machine dependent setup time precedes the processing of each batch. Jobs of the same batch are processed on each machine sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs of the same batch formed on machine l become available for a downstream operation on machine l+1 at the same time when the processing of the last job of the batch on machine l has been finished. The objective is to minimize maximum job completion time. We establish several properties of an optimal schedule and develop polynomial time algorithms for important special cases. They are improvements over the existing methods with regard to their generality and time efficiency.     

Bicriteria robotic cell scheduling

This paper considers the scheduling problems arising in two- and three-machine manufacturing cells configured in a flowshop which repeatedly produces one type of product and where transportation of the parts between the machines is performed by a robot. The cycle time of the cell is affected by the robot move sequence as well as the processing times of the parts on the machines. For highly flexible CNC machines, the processing times can be changed by altering the machining conditions at the expense of increasing the manufacturing cost. As a result, we try to find the robot move sequence as well as the processing times of the parts on each machine that not only minimize the cycle time but, for the first time in robotic cell scheduling literature, also minimize the manufacturing cost. For each 1-unit cycle in two- and three-machine cells, we determine the efficient set of processing time vectors such that no other processing time vector gives both a smaller cycle time and a smaller cost value. We also compare these cycles with each other to determine the sufficient conditions under which each of the cycles dominates the rest. Finally, we show how different assumptions on cost structures affect the results.     

Scheduling identical parallel machines and operators within a period based changing mode

This article addresses the problem of scheduling n non-preemptive jobs on m identical parallel machines with ω operators to minimize the makespan. The number of operators is less than the number of machines. As a result, it may happen that an operator has to supervise simultaneously several machines. This in turn has an impact on the job processing times as they become a function of the operators modus operandi. In this paper we consider the case where each modus operandi can only be changed at the end of a given period, i.e., a period based changing mode. We present heuristic algorithms to solve this problem. An experimental study is conducted to evaluate the performance of these heuristics in the average case, and a worst case analysis is presented for one of them.     

Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains

We study a supply chain scheduling problem in which n jobs have to be scheduled on a single machine and delivered to m customers in batches. Each job has a due date, a processing time and a lateness penalty (weight). To save batch-delivery costs, several jobs for the same customer can be delivered together in a batch, including late jobs. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time has to be added before processing the first job in each batch. The objective is to find a schedule which minimizes the sum of the weighted number of late jobs and the delivery costs. We present a pseudo-polynomial algorithm for a restricted case, where late jobs are delivered separately, and show that it becomes polynomial for the special cases when jobs have equal weights and equal delivery costs or equal processing times and equal setup times. We convert the algorithm into an FPTAS and prove that the solution produced by it is near-optimal for the original general problem by performing a parametric analysis of its performance ratio.     

Calibrations scheduling with arbitrary lengths and activation length

Bender et al. (SPAA 2013) proposed a theoretical framework for testing in contexts where safety mistakes must be avoided. Testing in such a context is made by machines that need to be calibrated on a regular basis. Since calibrations have a non-negligible cost, it is important to study policies minimizing the total calibration cost while performing all the necessary tests. We focus on the single-machine setting, and we study the complexity status of different variants of the problem. First, we extend the model by considering that the jobs have arbitrary processing times, and we propose an optimal polynomial-time algorithm when the preemption of jobs is allowed. Then, we study the case where there are many types of calibrations with their corresponding lengths and costs. We prove that the problem becomes NP-hard for arbitrary processing times even when the preemption of the jobs is allowed. Finally, we focus on the case of unit processing time jobs, and we show that a more general problem, where the recalibration of the machine is not instantaneous, can be solved in polynomial time via dynamic programming.

     

On a pair of job-machine assignment problems with two stages

We consider two assignment problems in which a number of jobs are assigned to the same number of machines that operate in parallel, but in two stages. They are known as the ‘2-stage time minimizing assignment problem’ and the ‘bi-level time minimizing assignment problem’. These problems have the following characteristics in common:

• Each of the machines processes one job (non-preemptively, without help of other machines).

• The job-machine assignments are partitioned into two successive stages of parallel processing.

• The objective is to minimize the makespan, the sum of the primary and the secondary completion time.

Both problems can be solved by (a series of) assignment problems. We improve the related computational complexities by applying reoptimization. Under some conditions a quadratic complexity is derived.We introduce a parameter weighing the relative importance of the primary and the secondary cost per time unit. The parametric problems can be solved, for all parameter values simultaneously, within the same reduced time complexity bounds.

Scope and purpose

As it is often important to solve problems quickly, it is essential to reduce the computational complexity of available algorithms, as far as possible. We consider two problems which arise when parallel scheduling is done in two successive stages; they can be tackled by solving a series of linear assignment problems. We show that they can be solved more efficiently, using properties of the classical linear assignment problem.In practice, the cost per time unit in the two stages need not be equal. A parameter controlling the ratio between these costs defines a parametric version of each problem. The algorithms of reduced time complexity can be extended to these parametric problem versions.     

Online batch scheduling on parallel machines with delivery times

We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4, we present an online algorithm with a competitive ratio of 1.5+o(1).     

Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time

We consider the two-machine flowshop scheduling problem where jobs have random processing times which are bounded within certain intervals. The objective is to minimize total completion time of all jobs. The decision of finding a solution for the problem has to be made based on the lower and upper bounds on job processing times since this is the only information available. The problem is NP-hard since the special case when the lower and upper bounds are equal, i.e., the deterministic case, is known to be NP-hard. Therefore, a reasonable approach is to come up with well performing heuristics. We propose eleven heuristics which utilize the lower and upper bounds on job processing times based on the Shortest Processing Time (SPT) rule. The proposed heuristics are compared through randomly generated data. The computational analysis has shown that the heuristics using the information on the bounds of job processing times on both machines perform much better than those using the information on one of the two machines. It has also shown that one of the proposed heuristics performs as the best for different distributions with an overall average percentage error of less than one.