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.     

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     

Scheduling parallel machines with inclusive processing set restrictions

We consider the problem of assigning a set of jobs to different parallel machines of the same processing speed, where each job is compatible to 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. The objective is to minimize the makespan of the schedule. This problem is motivated by industrial applications such as cargo handling by cranes with nonidentical weight capacities, computer processor scheduling with memory constraints, and grades of service provision by parallel servers. We develop an efficient algorithm for this problem with a worst‐case performance ratio of + ε, where ε is a positive constant which may be set arbitrarily close to zero. We also present a polynomial time approximation scheme for this problem, which answers an open question in the literature. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times

We investigate a single‐machine scheduling problem for which both the job processing times and due windows are decision variables to be determined by the decision maker. The job processing times are controllable as a linear or convex function of the amount of a common continuously divisible resource allocated to the jobs, where the resource allocated to the jobs can be used in discrete or continuous quantities. We use the common flow allowances due window assignment method to assign due windows to the jobs. We consider two performance criteria: (i) the total weighted number of early and tardy jobs plus the weighted due window assignment cost, and (ii) the resource consumption cost. For each resource consumption function, the objective is to minimize the first criterion, while keeping the value of the second criterion no greater than a given limit. We analyze the computational complexity, devise pseudo‐polynomial dynamic programming solution algorithms, and provide fully polynomial‐time approximation schemes and an enhanced volume algorithm to find high‐quality solutions quickly for the considered problems. We conduct extensive numerical studies to assess the performance of the algorithms. The computational results show that the proposed algorithms are very efficient in finding optimal or near‐optimal solutions. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 41–63, 2017     

Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost

Motivated by the flow of products in the iron and steel industry, we study an identical and parallel machine scheduling problem with batch deliveries, where jobs finished on the parallel machines are delivered to customers in batches. Each delivery batch has a capacity and incurs a cost. The objective is to find a coordinated production and delivery schedule that minimizes the total flow time of jobs plus the total delivery cost. This problem is an extension of the problem considered by Hall and Potts, Ann Oper Res 135 (2005) 41–64, who studied a two‐machine problem with an unbounded number of transporters and unbounded delivery capacity. We first provide a dynamic programming algorithm to solve a special case with a given job assignment to the machines. A heuristic algorithm is then presented for the general problem, and its worst‐case performance ratio is analyzed. The computational results show that the heuristic algorithm can generate near‐optimal solutions. Finally, we offer a fully polynomial‐time approximation scheme for a fixed number of machines. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 492–502, 2016     

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     

An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines

We consider the multitasking scheduling problem on unrelated parallel machines to minimize the total weighted completion time. In this problem, each machine processes a set of jobs, while the processing of a selected job on a machine may be interrupted by other available jobs scheduled on the same machine but unfinished. To solve this problem, we propose an exact branch‐and‐price algorithm, where the master problem at each search node is solved by a novel column generation scheme, called in‐out column generation, to maintain the stability of the dual variables. We use a greedy heuristic to obtain a set of initial columns to start the in‐out column generation, and a hybrid strategy combining a genetic algorithm and an exact dynamic programming algorithm to solve the pricing subproblems approximately and exactly, respectively. Using randomly generated data, we conduct numerical studies to evaluate the performance of the proposed solution approach. We also examine the effects of multitasking on the scheduling outcomes, with which the decision maker can justify making investments to adopt or avoid multitasking.     

Order-preserving allocation of jobs to two machines

In this paper, we consider the problem of minimizing the mean flow time of jobs to be processed on two machines. The jobs have a predetermined order, perhaps reflecting the order of arrival, and each job has a known processing time. We wish to assign the jobs to machines so as to minimize the mean flow time, with the constraint that the original order must be preserved within the subset of jobs assigned to each machine. An efficient algorithm based on dynamic programming is developed.     

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     

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     

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     

Due‐window assignment with unit processing‐time jobs

In due‐window assignment problems, jobs completed within a designated time interval are regarded as being on time, whereas early and tardy jobs are penalized. The objective is to determine the location and size of the due‐window, as well as the job schedule. We address a common due‐window assignment problem on parallel identical machines with unit processing time jobs. We show that the number of candidate values for the optimal due‐window starting time and for the optimal due‐window completion time are bounded by 2. We also prove that the starting time of the first job on each of the machines is either 0 or 1, thus introducing a fairly simple, constant‐time solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Scheduling jobs,with exponentially distributed processing times,on two machines of a flow shop

This paper treats the problem of sequencing n jobs on two machines in a “flow shop.” (That is, each job in the shop is required to flow through the same sequence of the machines.) The processing time of a given job on a given machine is assumed to be distributed exponentially, with a known mean. The objective is to minimize the expected job completion time. This paper proves an optimal ordering rule, previously conjectured by Talwar [10]. A formula is also derived through Markov Chain analysis, which evaluates the expected job completion time for any given sequence of the jobs. In addition, the performance of a heuristic rule is discussed in the light of the optimal solution.     

Scheduling parallel machines with inclusive processing set restrictions and job rejection

In this article, we study a parallel machine scheduling problem with inclusive processing set restrictions and the option of job rejection. In the problem, each job is compatible to a subset of machines, and machines are linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process (but not conversely). To achieve a tight production due date, some of the jobs might be rejected at certain penalty. We first study the problem of minimizing the makespan of all accepted jobs plus the total penalty cost of all rejected jobs, where we develop a ‐approximation algorithm with a time complexity of . We then study two bicriteria variants of the problem. For the variant problem of minimizing the makespan subject to a given bound on the total rejection cost, we develop a ‐approximation algorithm with a time complexity of . For the variant problem of maximizing the total rejection cost of the accepted jobs subject to a given bound on the makespan, we present a 0.5‐approximation algorithm with a time complexity of . © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 667–681, 2017     

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     

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

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     

Parallel machine scheduling with job assignment restrictions

In the classical multiprocessor scheduling problem independent jobs must be assigned to parallel, identical machines with the objective of minimizing the makespan. This article explores the effect of assignment restrictions on the jobs for multiprocessor scheduling problems. This means that each job can only be processed on a specific subset of the machines. Particular attention is given to the case of processing times restricted to one of two values, 1 and λ, differing by at most 2. A matching based polynomial time ε‐approximation algorithm is developed that has a performance ratio tending to . This algorithm is shown to have the best possible performance, tending to 3/2, for processing times 1 and 2. For the special case of nested processing sets, i.e., when the sets of machines upon which individual jobs may be assigned are non‐overlapping, the behavior of list scheduling algorithms is explored. Finally, for assignment restrictions determined by just one characteristic of the machines, such as disc storage or memory constraint in the case of high performance computing, we contribute an algorithm that provides a 3/2 worst case bound and runs in time linear in the number of jobs. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function

We consider open‐shop scheduling problems where operation‐processing times are a convex decreasing function of a common limited nonrenewable resource. The scheduler's objective is to determine the optimal job sequence on each machine and the optimal resource allocation for each operation in order to minimize the makespan. We prove that this problem is NP‐hard, but for the special case of the two‐machine problem we provide an efficient optimization algorithm. We also provide a fully polynomial approximation scheme for solving the preemptive case. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Two-agent scheduling with linear resource-dependent processing times

This paper considers a two-agent scheduling problem with linear resource-dependent processing times, in which each agent has a set of jobs that compete with that of the other agent for the use of a common processing machine, and each agent aims to minimize the weighted number of its tardy jobs. To meet the due date requirements of the jobs of the two agents, additional amounts of a common resource, which may be in discrete or continuous quantities, can be allocated to the processing of the jobs to compress their processing durations. The actual processing time of a job is a linear function of the amount of the resource allocated to it. The objective is to determine the optimal job sequence and resource allocation strategy so as to minimize the weighted number of tardy jobs of one agent, while keeping the weighted number of tardy jobs of the other agent, and the total resource consumption cost within their respective predetermined limits. It is shown that the problem is -hard in the ordinary sense, and there does not exist a polynomial-time approximation algorithm with performance ratio unless ; however it admits a relaxed fully polynomial time approximation scheme. A proximal bundle algorithm based on Lagrangian relaxation is also presented to solve the problem approximately. To speed up convergence and produce sharp bounds, enhancement strategies including the design of a Tabu search algorithm and integration of a Lagrangian recovery heuristic into the algorithm are devised. Extensive numerical studies are conducted to assess the effectiveness and efficiency of the proposed algorithms.