Adjacent orderings in single-machine scheduling with earliness and tardiness penalties

This article deals with a single-machine n job earliness-tardiness model with job-independent penalties. It demonstrates that the arrangement of adjacent jobs in an optimal schedule depends on a critical value of the start times. Based on these precedence relations, the article develops criteria under which the problem can be decomposed into smaller subproblems. The branching scheme that used the developed results was tested on 70 examples of size n = 10. This scheme should be incorporated in any branch-and-bound method once a lower bound is found. The branching scheme can easily handle small problems without a lower bound. © 1993 John Wiley & Sons, Inc.     

Minimizing the sum of weighted completion times of n-independent jobs when resource availability varies over time: Performance of a simple priority rule

In this article our objective is to evaluate the performance of a WSPT (weighted shortest processing time) rule for scheduling n independent jobs where the resources to process these jobs vary over time and a job can be processed by several processors simultaneously. This problem was raised by Baker and Nuttle [2]. A linear-programming (LP) model is formulated to obtain a lower bound on the minimum value of the weighted completion times. The purpose of the model is to provide a basis for evaluating the WSPT heuristic. 1000 experiments were performed using different resource profiles to test the performance of WSPT. Using WSPT, the weighted completion times were found to be, on the average, 0.2% away from their LP lower bounds.     

Strategic investment to reduce setup times in the economic lot scheduling problem

This article considers the Economic Lot Scheduling Problem where setup times and costs can be reduced by an initial investment that is amortized over time. The objective is to determine a multiple-item single facility cyclic schedule to minimize the long run average holding and setup costs plus the amortized investment. We develop a lower bound on the long run average inventory carrying and setup costs as a function of the setup times, and show that this lower bound is increasing concave on the setup times when the out-of-pocket setup costs are zero or proportional to the setup times. We then develop a model that may be helpful in deciding the magnitude and the distribution of a one-time investment in reducing the setup times when the investment is amortized over time. Numerical results based on randomly generated problems, and on Bomberger's ten item problem indicate that significant overall savings are possible for highly utilized facilities. Most of the savings are due to a significant reduction in the long run average holding cost. © 1995 John Wiley & Sons, Inc.     

Aggregating courier deliveries

We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ ? 1) ‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.     

A primal-dual algorithm for the dynamic lotsizing problem with joint set-up costs

In this article the multi-item dynamic lotsizing problem with joint set-up costs (LPJS) is considered. A tight formulation of the problem and the dual of the linear relaxation of this formulation is presented. A procedure to solve this dual problem is developed where the solution provides a strong lower bound for the LPJS. This lower bound is used in a branch and bound procedure to find an optimal solution to the problem. The extensive computational experiments with this procedure revealed that it outperforms the other available branch and bound algorithm in the literature. With the proposed algorithm the average time requirement was about 113 seconds on a 486DX33 processor for solving a difficult class of LPJS problems that have 50 items and 24 periods. © 1995 John Wiley & Sons, Inc.     

Scheduling of parallel processors: A posterior bound on LPT sequencing and a two-step algorithm

This article considers the problem of scheduling parallel processors to minimize the makespan. The article makes two key contributions: (1) It develops a new lower bound on the makespan for an optimal schedule, and (2) it proposes an efficient two-step algorithm to find schedules of any desired accuracy, or percent above optimal. In addition, a posterior bound on LPT (longest processing time) sequencing is developed in the article. It is proved that this bound dominates the previously reported bounds on LPT sequencing.     

Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times

We study a stochastic outpatient appointment scheduling problem (SOASP) in which we need to design a schedule and an adaptive rescheduling (i.e., resequencing or declining) policy for a set of patients. Each patient has a known type and associated probability distributions of random service duration and random arrival time. Finding a provably optimal solution to this problem requires solving a multistage stochastic mixed‐integer program (MSMIP) with a schedule optimization problem solved at each stage, determining the optimal rescheduling policy over the various random service durations and arrival times. In recognition that this MSMIP is intractable, we first consider a two‐stage model (TSM) that relaxes the nonanticipativity constraints of MSMIP and so yields a lower bound. Second, we derive a set of valid inequalities to strengthen and improve the solvability of the TSM formulation. Third, we obtain an upper bound for the MSMIP by solving the TSM under the feasible (and easily implementable) appointment order (AO) policy, which requires that patients are served in the order of their scheduled appointments, independent of their actual arrival times. Fourth, we propose a Monte Carlo approach to evaluate the relative gap between the MSMIP upper and lower bounds. Finally, in a series of numerical experiments, we show that these two bounds are very close in a wide range of SOASP instances, demonstrating the near‐optimality of the AO policy. We also identify parameter settings that result in a large gap in between these two bounds. Accordingly, we propose an alternative policy based on neighbor‐swapping. We demonstrate that this alternative policy leads to a much tighter upper bound and significantly shrinks the gap.     

Scheduling tasks with sequence-dependent processing times

In this article we consider the problem of minimizing the maximum completion time of a sequence of n jobs on a single machine. Nonzero ready times and sequence-dependent processing times are allowed. Upper bounds, lower bounds, and dominance criteria are proposed and exploited in a branch-and-bound algorithm. Computational results are given.     

The vehicle-routing problem with delivery and back-haul options

In this article we consider a version of the vehicle-routing problem (VRP): A fleet of identical capacitated vehicles serves a system of one warehouse and N customers of two types dispersed in the plane. Customers may require deliveries from the warehouse, back hauls to the warehouse, or both. The objective is to design a set of routes of minimum total length to serve all customers, without violating the capacity restriction of the vehicles along the routes. The capacity restriction here, in contrast to the VRP without back hauls is complicated because amount of capacity used depends on the order the customers are visited along the routes. The problem is NP-hard. We develop a lower bound on the optimal total cost and a heuristic solution for the problem. The routes generated by the heuristic are such that the back-haul customers are served only after terminating service to the delivery customers. However, the heuristic is shown to converge to the optimal solution, under mild probabilistic conditions, as fast as N^−0.5. The complexity of the heuristic, as well as the computation of the lower bound, is O(N³) if all customers have unit demand size and O(N³ log N) otherwise, independently of the demand sizes. © 1996 John Wiley & Sons, Inc.     

Minimizing the weighted sum of quadratic completion times on a single machine

This article discusses the scheduling problem of minimizing the weighted sum of quadratic completion times on a single machine. It establishes links between orderings of adjacent and nonadjacent jobs that lead to a powerful branch and bound method. Computational results show that this method clearly outperforms the state of the art algorithm. © 1995 John Wiley & Sons. Inc.     

Solvable cases of the flow-shop problem without interruptions in job processing

This article examines solvable cases of the flow-shop problem without interruptions in job processing where the completion time is being minimized. All those cases utilize Gilmore-Gomory's algorithm. A lower completion time bound is also provided.     

Distribution free bounds for service constrained (Q,r) inventory systems

A classical and important problem in stochastic inventory theory is to determine the order quantity (Q) and the reorder level (r) to minimize inventory holding and backorder costs subject to a service constraint that the fill rate, i.e., the fraction of demand satisfied by inventory in stock, is at least equal to a desired value. This problem is often hard to solve because the fill rate constraint is not convex in (Q, r) unless additional assumptions are made about the distribution of demand during the lead‐time. As a consequence, there are no known algorithms, other than exhaustive search, that are available for solving this problem in its full generality. Our paper derives the first known bounds to the fill‐rate constrained (Q, r) inventory problem. We derive upper and lower bounds for the optimal values of the order quantity and the reorder level for this problem that are independent of the distribution of demand during the lead time and its variance. We show that the classical economic order quantity is a lower bound on the optimal ordering quantity. We present an efficient solution procedure that exploits these bounds and has a guaranteed bound on the error. When the Lagrangian of the fill rate constraint is convex or when the fill rate constraint does not exist, our bounds can be used to enhance the efficiency of existing algorithms. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 635–656, 2000     

A branch and bound algorithm for the minimum storage‐time sequencing problem

The minimum storage‐time sequencing problem generalizes many well‐known problems in combinatorial optimization, such as the directed linear arrangement and the problem of minimizing the weighted sum of completion times, subject to precedence constraints on a single processor. In this paper we propose a new lower bound, based on a Lagrangian relaxation, which can be computed very efficiently. To improve upon this lower bound, we employ a bundle optimization algorithm. We also show that the best bound obtainable by this approach equals the one obtainable from the linear relaxation computed on a formulation whose first Chvàtal closure equals the convex hull of all the integer solutions of the problem. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 313–331, 2001     

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     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

A branch-and-bound algorithm to minimize total tardiness with different release dates

This article deals with the scheduling problem for minimizing total tardiness with unequal release dates. A set of jobs have to be scheduled on a machine able to perform only one job at a time. No preemptive job is allowed. This problem has been proven to be NP-hard. We prove some dominance properties, and provide a lower bound polynomially computed for this problem. On the basis of our previous results, we propose a branch-and-bound algorithm to solve the problem. This algorithm was tested on hard problems involving 30 jobs and also on relatively easy problems with up to 230 jobs. Detailed computational results are given.     

On online bin packing with LIB constraints

In many applications of packing, the location of small items below large items, inside the packed boxes, is forbidden. We consider a variant of the classic online one‐dimensional bin packing, in which items allocated to each bin are packed there in the order of arrival, satisfying the condition above. This variant is called online bin packing problem with LIB (larger item in the bottom) constraints. We give an improved analysis of First Fit showing that its competitive ratio is at most , and design a lower bound of 2 on the competitive ratio of any online algorithm. In addition, we study the competitive ratio of First Fit as a function of an upper bound (where d is a positive integer) on the item sizes. Our upper bound on the competitive ratio of First Fit tends to 2 as d grows, whereas the lower bound of two holds for any value of d. Finally, we consider several natural and well known algorithms, namely, Best Fit, Worst Fit, Almost Worst Fit, and Harmonic, and show that none of them has a finite competitive ratio for the problem. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems

Until recently, fast algorithms for the maximum flow problem have typically proceeded by constructing layered networks and establishing blocking flows in these networks. However, in recent years, new distance-directed algorithms have been suggested that do not construct layered networks but instead maintain a distance label with each node. The distance label of a node is a lower bound on the length of the shortest augmenting path from the node to the sink. In this article we develop two distance-directed augmenting path algorithms for the maximum flow problem. Both the algorithms run in O(n²m) time on networks with n nodes and m arcs. We also point out the relationship between the distance labels and layered networks. Using a scaling technique, we improve the complexity of our distance-directed algorithms to O(nm log U), where U denotes the largest arc capacity. We also consider applications of these algorithms to unit capacity maximum flow problems and a class of parametric maximum flow problems.     

The quadratic minimum spanning tree problem

This article introduces a new optimization problem that involves searching for the spanning tree of minimum cost under a quadratic cost structure. This quadratic minimum spanning tree problem is proven to be NP-hard. A technique for generating lower bounds for this problem is discussed and incorporated into branch-and-bound schemes for obtaining exact solutions. Two heuristic algorithms are also developed. Computational experience with both exact and heuristic algorithms is reported.     

Heuristics for multimachine minmax scheduling problems with general earliness and tardiness costs

We consider the problem of scheduling N jobs on M parallel machines so as to minimize the maximum earliness or tardiness cost incurred for each of the jobs. Earliness and tardiness costs are given by general (but job-independent) functions of the amount of time a job is completed prior to or after a common due date. We show that in problems with a nonrestrictive due date, the problem decomposes into two parts. Each of the M longest jobs is assigned to a different machine, and all other jobs are assigned to the machines so as to minimize their makespan. With these assignments, the individual scheduling problems for each of the machines are simple to solve. We demonstrate that several simple heuristics of low complexity, based on this characterization, are asymptotically optimal under mild probabilistic conditions. We develop attractive worst-case bounds for them. We also develop a simple closed-form lower bound for the minimum cost value. The bound is asymptotically accurate under the same probabilistic conditions. In the case where the due date is restrictive, the problem is more complex only in the sense that the set of initial jobs on the machines is not easily characterized. However, we extend our heuristics and lower bounds to this general case as well. Numerical studies exhibit that these heuristics perform excellently even for small- or moderate-size problems both in the restrictive and nonrestrictive due-date case. © 1997 John Wiley & Sons, Inc.