Scheduling parallel dedicated machines with the speeding‐up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two‐machine problem is NP‐hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst‐case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple‐choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Production scheduling with history‐dependent setup times

We consider a parallel‐machine scheduling problem with jobs that require setups. The duration of a setup does not depend only on the job just completed but on a number of preceding jobs. These setup times are referred to as history‐dependent. Such a scheduling problem is often encountered in the food processing industry as well as in other process industries. In our model, we consider two types of setup times—a regular setup time and a major setup time that becomes necessary after several “hard‐to‐clean” jobs have been processed on the same machine. We consider multiple objectives, including facility utilization, flexibility, number of major setups, and tardiness. We solve several special cases assuming predetermined job sequences and propose strongly polynomial time algorithms to determine the optimal timing of the major setups for given job sequences. We also extend our analysis to develop pseudopolynomial time algorithms for cases with additional objectives, including the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Scheduling jobs and maintenance activities on parallel machines

Most machine scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines need to be maintained and hence may become unavailable during certain periods. In this paper, we study the problem of processing a set of n jobs on m parallel machines where each machine must be maintained once during the planning horizon. Our objective is to schedule jobs and maintenance activities so that the total weighted completion time of jobs is minimized. Two cases are studied in this paper. In the first case, there are sufficient resources so that different machines can be maintained simultaneously if necessary. In the second case, only one machine can be maintained at any given time. In this paper, we first show that, even when all jobs have the same weight, both cases of the problem are NP-hard. We then propose branch and bound algorithms based on the column generation approach for solving both cases of the problem. Our algorithms are capable of optimally solving medium sized problems within a reasonable computational time. We note that the general problem where at most j machines, 1 ≤ j ≤ m, can be maintained simultaneously, can be solved similarly by the column generation approach proposed in this paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 145–165, 2000     

Machine scheduling with an availability constraint and job delivery coordination

In this paper we study the scheduling problem that considers both production and job delivery at the same time with machine availability considerations. Only one vehicle is available to deliver jobs in a fixed transportation time to a distribution center. The vehicle can load at most K jobs as a delivery batch in one shipment due to the vehicle capacity constraint. The objective is to minimize the arrival time of the last delivery batch to the distribution center. Since machines may not always be available over the production period in real life due to preventive maintenance, we incorporate machine availability into the models. Three scenarios of the problem are studied. For the problem in which the jobs are processed on a single machine and the jobs interrupted by the unavailable machine interval are resumable, we provide a polynomial algorithm to solve the problem optimally. For the problem in which the jobs are processed on a single machine and the interrupted jobs are nonresumable, we first show that the problem is NP‐hard. We then propose a heuristic with a worst‐case error bound of 1/2 and show that the bound is tight. For the problem in which the jobs are processed on either one of two parallel machines, where only one machine has an unavailable interval and the interrupted jobs are resumable, we propose a heuristic with a worst‐case error bound of 2/3. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Scheduling maintenance and semiresumable jobs on a single machine

The majority of scheduling literature assumes that the machines are available at all times. In this paper, we study single machine scheduling problems where the machine maintenance must be performed within certain intervals and hence the machine is not available during the maintenance periods. We also assume that if a job is not processed to completion before the machine is stopped for maintenance, an additional setup is necessary when the processing is resumed. Our purpose is to schedule the maintenance and jobs to minimize some performance measures. The objective functions that we consider are minimizing the total weighted job completion times and minimizing the maximum lateness. In both cases, maintenance must be performed within a fixed period T, and the time for the maintenance is a decision variable. In this paper, we study two scenarios concerning the planning horizon. First, we show that, when the planning horizon is long in relation to T, the problem with either objective function is NP-complete, and we present pseudopolynomial time dynamic programming algorithms for both objective functions. In the second scenario, the planning horizon is short in relation to T. However, part of the period T may have elapsed before we schedule any jobs in this planning horizon, and the remaining time before the maintenance is shorter than the current planning horizon. Hence we must schedule one maintenance in this planning horizon. We show that the problem of minimizing the total weighted completion times in this scenario is NP-complete, while the shortest processing time (SPT) rule and the earliest due date (EDD) rule are optimal for the total completion time problem and the maximum lateness problem respectively. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 845–863, 1999     

Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations

We study a single batching machine scheduling problem with transportation and deterioration considerations arising from steel production. A set of jobs are transported, one at a time, by a vehicle from a holding area to the single batching machine. The machine can process several jobs simultaneously as a batch. The processing time of a job will increase if the duration from the time leaving the holding area to the start of its processing exceeds a given threshold. The time needed to process a batch is the longest of the job processing times in the batch. The problem is to determine the job sequence for transportation and the job batching for processing so as to minimize the makespan and the number of batches. We study four variations (P1, P2, P3, P4) of the problem with different treatments of the two criteria. We prove that all the four variations are strongly NP‐hard and further develop polynomial time algorithms for their special cases. For each of the first three variations, we propose a heuristic algorithm and analyze its worst‐case performance. For P4, which is to find the Pareto frontier, we provide a heuristic algorithm and an exact algorithm based on branch and bound. Computational experiments show that all the heuristic algorithms perform well on randomly generated problem instances, and the exact algorithm for P4 can obtain Pareto optimal schedules for small‐scale instances. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 269–285, 2014     

Server scheduling on parallel dedicated machines with fixed job sequences

We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial‐time algorithm to solve the two‐machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP‐hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.     

On‐line algorithms for minimizing makespan on batch processing machines

We consider problem of scheduling jobs on‐line on batch processing machines with dynamic job arrivals to minimize makespan. A batch machine can handle up to B jobs simultaneously. The jobs that are processed together from a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on‐line algorithms with worst‐case ratio (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst‐case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bound are given, and two on‐line algorithms are presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258, 2001     

The effectiveness of the longest delivery time rule for the flow shop delivery time problem

In the flow shop delivery time problem, a set of jobs has to be processed on m machines. Every machine has to process each one of the jobs, and every job has the same routing through the machines. The objective is to determine a sequence of the jobs on the machines so as to minimize maximum delivery completion time over all the jobs, where the delivery completion time of a job is the sum of its completion time, and the delivery time associated with that job. In this paper, we prove the asymptotic optimality of the Longest Delivery Time algorithm for the static version of this problem, and the Longest Delivery Time among Available Jobs (LDTA) algorithm for the dynamic version of this problem. In addition, we present the result of computational testing of the effectiveness of these algorithms. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 172–183, 2016     

Single machine just‐in‐time scheduling problems with two competing agents

In scheduling problems with two competing agents, each one of the agents has his own set of jobs to be processed and his own objective function, and both share a common processor. In the single‐machine problem studied in this article, the goal is to find a joint schedule that minimizes the total deviation of the job completion times of the first agent from a common due‐date, subject to an upper bound on the maximum deviation of job completion times of the second agent. The problem is shown to be NP‐hard even for a nonrestrictive due‐date, and a pseudopolynomial dynamic program is introduced and tested numerically. For the case of a restrictive due‐date (a sufficiently small due‐date that may restrict the number of early jobs), a faster pseudopolynomial dynamic program is presented. We also study the multiagent case, which is proved to be strongly NP‐hard. A simple heuristic for this case is introduced, which is tested numerically against a lower bound, obtained by extending the dynamic programming algorithm. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 1–16, 2014     

CON/SLK due date assignment and scheduling on a single machine with two agents

We consider scheduling problems involving two agents (agents A and B), each having a set of jobs that compete for the use of a common machine to process their respective jobs. The due dates of the A‐jobs are decision variables, which are determined by using the common (CON) or slack (SLK) due date assignment methods. Each agent wants to minimize a certain performance criterion depending on the completion times of its jobs only. Under each due date assignment method, the criterion of agent A is always the same, namely an integrated criterion consisting of the due date assignment cost and the weighted number of tardy jobs. Several different criteria are considered for agent B, including the maxima of regular functions (associated with each job), the total (weighted) completion time, and the weighted number of tardy jobs. The overall objective is to minimize the performance criterion of agent A, while keeping the objective value of agent B no greater than a given limit. We analyze the computational complexity, and devise polynomial or pseudo‐polynomial dynamic programming algorithms for the considered problems. We also convert, if viable, any of the devised pseudopolynomial dynamic programming algorithms into a fully polynomial‐time approximation scheme. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 416–429, 2016     

Minimizing makespan on a single batch processing machine with nonidentical job sizes

We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst‐case ratio 3/2 is given for the version where the processing times of large jobs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst‐case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 226–240, 2001     

Opportunistic retooling of a flexible machine subject to failure

A set of jobs can be processed without interruption by a flexible machine only if the set of tools required by all jobs can be loaded in the tool magazine. However, in practice the total number of tools required by a job set would exceed the tool magazine capacity. In such situations, the job set has to be carefully partitioned at the start of the production run such that each partition can be processed without interruption. During the production run, if there are unscheduled machine downtimes due to machine failure, this provides an additional opportunity to optimally retool the magazine for a smaller job set consisting of just the unprocessed jobs. In this paper, we study job sequencing rules that allow us to minimize the total expected cost of machine down time due to machine failures and magazine retooling, assuming a dynamic re‐sequencing of the unprocessed jobs after each machine failure. Using these rules, we develop a branch‐and‐bound heuristic that allows us to solve problems of reasonable size. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 79–97, 2001     

Minimizing weighted mean absolute deviation of flow times in single machine systems

We discuss the problem of scheduling several jobs on a single machine with the objective of minimizing the weighted mean absolute deviation of flow times around the weighted mean flow time. We first show that the optimal schedule is W-shaped. For the unweighted case, we show that all optimal schedules are V-shaped. This characterization enables us to show that the problem is NP-hard. We then provide a pseudopolynomial algorithm for the unweighted problem. Finally, we consider three heuristic algorithms for the unweighted problem and report computational experience with these algorithms. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 297–311, 1998     

Open shop scheduling to minimize the number of late jobs

We develop polynomial algorithms for several cases of the NP-hard open shop scheduling problem of minimizing the number of late jobs by utilizing some recent results for the open shop makespan problem. For the two machine common due date problem, we assume that either the machines or the jobs are ordered. For the m machine common due date problem, we assume that one machine is maximal and impose a restriction on its load. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 525–532, 1998     

Optimal assignment of high multiplicity flight plans to dispatchers

This paper addresses the problem of finding a feasible schedule of n jobs on m parallel machines, where each job has a deadline and some jobs are preassigned to some machine. This problem arises in the daily assignment of workload to a set of flight dispatchers, and it is strongly characterized by the fact that the job lengths may assume one out of k different values, for small k. We prove the problem to be NP‐complete for k = 2 and propose an effective implicit enumeration algorithm which allows efficiently solution a set of real‐life instances. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 359–376, 2000     

Scheduling jobs with piecewise linear decreasing processing times

We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP‐hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP‐hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 531–554, 2003     

A note on combined job selection and sequencing problems

We investigate the solvability of two single‐machine scheduling problems when the objective is to identify among all job subsets with cardinality k,1≤k≤n, the one that has the minimum objective function value. For the single‐machine minimum maximum lateness problem, we conclude that the problem is solvable in O(n²) time using the proposed REMOVE algorithm. This algorithm can also be used as an alternative to Moore's algorithm to solve the minimum number of tardy jobs problem by actually solving the hierarchical problem in which the objective is to minimize the maximum lateness subject to the minimum number of tardy jobs. We then show that the REMOVE algorithm cannot be used to solve the general case of the single‐machine total‐weighted completion time problem; we derive sufficient conditions among the job parameters so that the total weighted completion time problem becomes solvable in O(n²) time. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 449–453, 2013     

Single‐machine scheduling with deadlines to minimize the total weighted late work

We consider scheduling a set of jobs with deadlines to minimize the total weighted late work on a single machine, where the late work of a job is the amount of processing of the job that is scheduled after its due date and before its deadline. This is the first study on scheduling with the late work criterion under the deadline restriction. In this paper, we show that (i) the problem is unary NP‐hard even if all the jobs have a unit weight, (ii) the problem is binary NP‐hard and admits a pseudo‐polynomial‐time algorithm and a fully polynomial‐time approximation scheme if all the jobs have a common due date, and (iii) some special cases of the problem are polynomially solvable.