The quay crane scheduling problem with time windows

The quay crane scheduling problem consists of scheduling tasks for loading and unloading containers on cranes that are assigned to a vessel for its service. This article introduces a new approach for quay crane scheduling, where the availability of cranes at a vessel is restricted to certain time windows. The problem is of practical relevance, because container terminal operators frequently redeploy cranes among vessels to speed up the service of high‐priority vessels while serving low‐priority vessels casually. This article provides a mathematical formulation of the problem and a tree‐search‐based heuristic solution method. A computational investigation on a large set of test instances is used to evaluate the performance of the heuristic and to identify the impact of differently structured crane time windows on the achievable vessel handling time. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Determining crane areas for balancing workload among interfering and noninterfering cranes

This article treats the problem of subdividing an area for storing containers such that the workload is evenly shared among the cranes operating the resulting subareas. We consider two crane sets: while noncrossing constraints between cranes of the same set need to be observed, cranes of different sets do not interfere. Such a problem setting is, for instance, relevant for scheduling the (un‐)loading of vessels by parallel quay cranes operating on opposing berths or in container yards with cross‐over cranes. We formalize the resulting optimization problem, prove computational complexity, and present exact and heuristic solution procedures. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Optimally scheduling interfering and non‐interfering cranes

This article treats the problem of scheduling multiple cranes processing jobs along a line, where cranes are divided into different groups and only cranes in the same group can interfere with each other. Such crane scheduling problems occur, for example, at indented berths or in container yards where double rail‐mounted gantry cranes stack containers such that cranes of the same size can interfere with each other but small cranes can pass underneath larger ones. We propose a novel algorithm based on Benders decomposition to solve this problem to optimality. In a computational study, it is shown that this algorithm solves small and medium‐sized instances and even many large instances within a few seconds or minutes. Moreover, it improves several best known solutions from the literature with regard to the simpler problem version with only one crane group. We also look into whether investment in more complicated crane configurations with multiple crane groups is actually worthwhile.     

Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures

In this paper, we study the problem of scheduling quay cranes (QCs) at container terminals where incoming vessels have different ready times. The objective is to minimize the maximum relative tardiness of vessel departures. The problem can be formulated as a mixed integer linear programming (MILP) model of large size that is difficult to solve directly. We propose a heuristic decomposition approach to breakdown the problem into two smaller, linked models, the vessel‐level and the berth‐level models. With the same berth‐level model, two heuristic methods are developed using different vessel‐level models. Computational experiments show that the proposed approach is effective and efficient. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A m‐parallel crane scheduling problem with a non‐crossing constraint

In this paper, we study a m‐parallel machine scheduling problem with a non‐crossing constraint motivated by crane scheduling in ports. We decompose the problem to allow time allocations to be determined once crane assignments are known and construct a backtracking search scheme that manipulates domain reduction and pruning strategies. Simple approximation heuristics are developed, one of which guarantees solutions to be at most two times the optimum. For large‐scale problems, a simulated annealing heuristic that uses random neighborhood generation is provided. Computational experiments are conducted to test the algorithms. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

Crane scheduling with spatial constraints

In this work, we examine port crane scheduling with spatial and separation constraints. Although common to most port operations, these constraints have not been previously studied. We assume that cranes cannot cross, there is a minimum distance between cranes and jobs cannot be done simultaneously. The objective is to find a crane‐to‐job matching which maximizes throughput under these constraints. We provide dynamic programming algorithms, a probabilistic tabu search, and a squeaky wheel optimization heuristic for solution. Experiments show the heuristics perform well compared with optimal solutions obtained by CPLEX for small scale instances where a squeaky wheel optimization with local search approach gives good results within short times. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Two‐agent scheduling on a single sequential and compatible batching machine

We study two‐agent scheduling on a single sequential and compatible batching machine in which jobs in each batch are processed sequentially and compatibility means that jobs of distinct agents can be processed in a common batch. A fixed setup time is required before each batch is started. Each agent seeks to optimize some scheduling criterion that depends on the completion times of its own jobs only. We consider several scheduling problems arising from different combinations of some regular scheduling criteria, including the maximum cost (embracing lateness and makespan as its special cases), the total completion time, and the (weighted) number of tardy jobs. Our goal is to find an optimal schedule that minimizes the objective value of one agent, subject to an upper bound on the objective value of the other agent. For each problem under consideration, we provide either a polynomial‐time or a pseudo‐polynomial‐time algorithm to solve it. We also devise a fully polynomial‐time approximation scheme when both agents’ scheduling criteria are the weighted number of tardy jobs.     

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     

Capacitated lot‐sizing and scheduling with parallel machines,back‐orders,and setup carry‐over

We address the capacitated lot‐sizing and scheduling problem with setup times, setup carry‐over, back‐orders, and parallel machines as it appears in a semiconductor assembly facility. The problem can be formulated as an extension of the capacitated lot‐sizing problem with linked lot‐sizes (CLSPL). We present a mixed integer (MIP) formulation of the problem and a new solution procedure. The solution procedure is based on a novel “aggregate model,” which uses integer instead of binary variables. The model is embedded in a period‐by‐period heuristic and is solved to optimality or near‐optimality in each iteration using standard procedures (CPLEX). A subsequent scheduling routine loads and sequences the products on the parallel machines. Six variants of the heuristic are presented and tested in an extensive computational study. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Flow‐shop batch scheduling with identical processing‐time jobs

In many practical situations of production scheduling, it is either necessary or recommended to group a large number of jobs into a relatively small number of batches. A decision needs to be made regarding both the batching (i.e., determining the number and the size of the batches) and the sequencing (of batches and of jobs within batches). A setup cost is incurred whenever a batch begins processing on a given machine. This paper focuses on batch scheduling of identical processing‐time jobs, and machine‐ and sequence‐independent setup times on an m‐machine flow‐shop. The objective is to find an allocation to batches and their schedule in order to minimize flow‐time. We introduce a surprising and nonintuitive solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

On equivalence between the proportionate flow shop and single‐machine scheduling problems

We derive sufficient conditions which, when satisfied, guarantee that an optimal solution for a single‐machine scheduling problem is also optimal for the corresponding proportionate flow shop scheduling problem. We then utilize these sufficient conditions to show the solvability in polynomial time of numerous proportionate flow shop scheduling problems with fixed job processing times, position‐dependent job processing times, controllable job processing times, and also problems with job rejection. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 595–603, 2015     

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     

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     

A self‐adapting genetic algorithm for project scheduling under resource constraints

This papers deals with the classical resource‐constrained project scheduling problem (RCPSP). There, the activities of a project have to be scheduled subject to precedence and resource constraints. The objective is to minimize the makespan of the project. We propose a new heuristic called self‐adapting genetic algorithm to solve the RCPSP. The heuristic employs the well‐known activity list representation and considers two different decoding procedures. An additional gene in the representation determines which of the two decoding procedures is actually used to compute a schedule for an individual. This allows the genetic algorithm to adapt itself to the problem instance actually solved. That is, the genetic algorithm learns which of the alternative decoding procedures is the more successful one for this instance. In other words, not only the solution for the problem, but also the algorithm itself is subject to genetic optimization. Computational experiments show that the mechanism of self‐adaptation is capable to exploit the benefits of both decoding procedures. Moreover, the tests show that the proposed heuristic is among the best ones currently available for the RCPSP. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 433–448, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10029     

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     

Analysis of algorithms for two‐stage flowshops with multi‐processor task flexibility

In this article we introduce a 2‐machine flowshop with processing flexibility. Two processing modes are available for each task: namely, processing by the designated processor, and processing simultaneously by both processors. The objective studied is makespan minimization. This production environment is encountered in repetitive manufacturing shops equipped with processors that have the flexibility to execute orders either individually or in coordination. In the latter case, the product designer exploits processing synergies between two processors so as to execute a particular task much faster than a dedicated processor. This type of flowshop environment is also encountered in labor‐intensive assembly lines where products moving downstream can be processed either in the designated assembly stations or by pulling together the work teams of adjacent stations. This scheduling problem requires determining the mode of operation of each task, and the subsequent scheduling that preserves the flowshop constraints. We show that the problem is ordinary NP‐complete and obtain an optimal solution using a dynamic programming algorithm with considerable computational requirements for medium and large problems. Then, we present a number of dynamic programming relaxations and analyze their worst‐case error performance. Finally, we present a polynomial time heuristic with worst‐case error performance comparable to that of the dynamic programming relaxations. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

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     

Two‐machine flow shop no‐wait scheduling with a nonavailability interval

We study a two‐machine flow shop scheduling problem with no‐wait in process, in which one of the machines is not available during a specified time interval. We consider three scenarios of handing the operation affected by the nonavailability interval. Its processing may (i) start from scratch after the interval, or (ii) be resumed from the point of interruption, or (iii) be partially restarted after the interval. The objective is to minimize the makespan. We present an approximation algorithm that for all these scenarios delivers a worst‐case ratio of 3/2. For the second scenario, we offer a 4/3‐approximation algorithm. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A branch‐and‐price approach for the stochastic generalized assignment problem

In this article, we address a stochastic generalized assignment machine scheduling problem in which the processing times of jobs are assumed to be random variables. We develop a branch‐and‐price (B&P) approach for solving this problem wherein the pricing problem is separable with respect to each machine, and has the structure of a multidimensional knapsack problem. In addition, we explore two other extensions of this method—one that utilizes a dual‐stabilization technique and another that incorporates an advanced‐start procedure to obtain an initial feasible solution. We compare the performance of these methods with that of the branch‐and‐cut (B&C) method within CPLEX. Our results show that all B&P‐based approaches perform better than the B&C method, with the best performance obtained for the B&P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&P scheme, which affords the use of a small subset of scenarios at a time to estimate the “true” optimal objective function value. Our experimental investigation reveals that this approach readily yields solutions lying within 5% of optimality, while providing more than a 10‐fold savings in CPU times in comparison with the best of the other proposed B&P procedures. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131–143, 2014     

Project scheduling under competition

We introduce and investigate the problem of scheduling activities of a project by a firm that competes with another firm (the competitor) that has to perform the same project. The profit that the firm gets from each activity depends on whether the firm finishes the activity before or after its competitor. The objective is to maximize the guaranteed (worst‐case) profit. We assume that both the firm and the competitor can perform only one activity at a time. We perform a detailed complexity analysis of the problem, and consider problems with and without precedence constraints, with and without delay of the competitor, with general and equal processing times of activities. For polynomially solvable cases (which include, for example, all the considered problems without delay of the competitor), we present easily implementable and intuitive rules that allow us to obtain optimal schedules in linear or almost linear time. For some NP‐hard cases, we present pseudopolynomial algorithms and fast heuristics with worst‐case approximation guarantees. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.