Hybrid heuristics for minimum cardinality set covering problems

Minimum cardinality set covering problems (MCSCP) tend to be more difficult to solve than weighted set covering problems because the cost or weight associated with each variable is the same. Since MCSCP is NP-complete, large problem instances are commonly solved using some form of a greedy heuristic. In this paper hybrid algorithms are developed and tested against two common forms of the greedy heuristic. Although all the algorithms tested have the same worst case bounds provided by Ho [7], empirical results for 60 large randomly generated problems indicate that one algorithm performed better than the others.     

An asymptotically optimal greedy heuristic for the multiperiod single‐sourcing problem: The cyclic case

The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single‐sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end‐of‐study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 412–437, 2003     

Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem

In this paper we propose some non‐greedy heuristics and develop an Augmented‐Neural‐Network (AugNN) formulation for solving the classical open‐shop scheduling problem (OSSP). AugNN is a neural network based meta‐heuristic approach that allows integration of domain‐specific knowledge. The OSSP is framed as a neural network with multiple layers of jobs and machines. Input, output and activation functions are designed to enforce the problem constraints and embed known heuristics to generate a good feasible solution fast. Suitable learning strategies are applied to obtain better neighborhood solutions iteratively. The new heuristics and the AugNN formulation are tested on several benchmark problem instances in the literature and on some new problem instances generated in this study. The results are very competitive with other meta‐heuristic approaches, both in terms of solution quality and computational times. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Scheduling of depalletizing and truck loading operations in a food distribution system

This paper studies a scheduling problem arising in a beef distribution system where pallets of various types of beef products in the warehouse are first depalletized and then individual cases are loaded via conveyors to the trucks which deliver beef products to various customers. Given each customer's demand for each type of beef, the problem is to find a depalletizing and truck loading schedule that fills all the demands at a minimum total cost. We first show that the general problem where there are multiple trucks and each truck covers multiple customers is strongly NP‐hard. Then we propose polynomial‐time algorithms for the case where there are multiple trucks, each covering only one customer, and the case where there is only one truck covering multiple customers. We also develop an optimal dynamic programming algorithm and a heuristic for solving the general problem. By comparing to the optimal solutions generated by the dynamic programming algorithm, the heuristic is shown to be capable of generating near optimal solutions quickly. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

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     

The stochastic single resource service‐provision problem

The service‐provision problem described in this paper comes from an application of distributed processing in telecommunications networks. The objective is to maximize a service provider's profit from offering computational‐based services to customers. The service provider has limited capacity and must choose which of a set of software applications he would like to offer. This can be done dynamically, taking into consideration that demand for the different services is uncertain. The problem is examined in the framework of stochastic integer programming. Approximations and complexity are examined for the case when demand is described by a discrete probability distribution. For the deterministic counterpart, a fully polynomial approximation scheme is known 2 . We show that introduction of stochasticity makes the problem strongly NP‐hard, implying that the existence of such a scheme for the stochastic problem is highly unlikely. For the general case a heuristic with a worst‐case performance ratio that increases in the number of scenarios is presented. Restricting the class of problem instances in a way that many reasonable practical problem instances satisfy allows for the derivation of a heuristic with a constant worst‐case performance ratio. Worst‐case performance analysis of approximation algorithms is classical in the field of combinatorial optimization, but in stochastic programming the authors are not aware of any previous results in this direction. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Models and algorithms for shuffling problems in steel plants

In this article, we study item shuffling (IS) problems arising in the logistics system of steel production. An IS problem here is to optimize shuffling operations needed in retrieving a sequence of steel items from a warehouse served by a crane. There are two types of such problems, plate shuffling problems (PSP) and coil shuffling problems (CSP), considering the item shapes. The PSP is modeled as a container storage location assignment problem. For CSP, a novel linear integer programming model is formulated considering the practical stacking and shuffling features. Several valid inequalities are constructed to accelerate the solving of the models. Some properties of optimal solutions of PSP and CSP are also derived. Because of the strong NP‐hardness of the problems, we consider some special cases of them and propose polynomial time algorithms to obtain optimal solutions for these cases. A greedy heuristic is proposed to solve the general problems and its worst‐case performances on both PSP and CSP are analyzed. A tabu search (TS) method with a tabu list of variable length is proposed to further improve the heuristic solutions. Without considering the crane traveling distance, we then construct a rolling variable horizon heuristic for the problems. Numerical experiments show that the proposed heuristic algorithms and the TS method are effective. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Heuristics for the location of inspection stations on a network

This article considers the preventive flow interception problem (FIP) on a network. Given a directed network with known origin‐destination path flows, each generating a certain amount of risk, the preventive FIP consists of optimally locating m facilities on the network in order to maximize the total risk reduction. A greedy search heuristic as well as several variants of an ascent search heuristic and of a tabu search heuristic are presented for the FIP. Computational results indicate that the best versions of the latter heuristics consistently produce optimal or near optimal solutions on test problems. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 287–303, 2000     

Scheduling a production–distribution system to optimize the tradeoff between delivery tardiness and distribution cost

We consider a make‐to‐order production–distribution system with one supplier and one or more customers. A set of orders with due dates needs to be processed by the supplier and delivered to the customers upon completion. The supplier can process one order at a time without preemption. Each customer is at a distinct location and only orders from the same customer can be batched together for delivery. Each delivery shipment has a capacity limit and incurs a distribution cost. The problem is to find a joint schedule of order processing at the supplier and order delivery from the supplier to the customers that optimizes an objective function involving the maximum delivery tardiness and the total distribution cost. We first study the solvability of various cases of the problem by either providing an efficient algorithm or proving the intractability of the problem. We then develop a fast heuristic for the general problem. We show that the heuristic is asymptotically optimal as the number of orders goes to infinity. We also evaluate the performance of the heuristic computationally by using lower bounds obtained by a column generation approach. Our results indicate that the heuristic is capable of generating near optimal solutions quickly. Finally, we study the value of production–distribution integration by comparing our integrated approach with two sequential approaches where scheduling decisions for order processing are made first, followed by order delivery decisions, with no or only partial integration of the two decisions. We show that in many cases, the integrated approach performs significantly better than the sequential approaches. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000     

A branch‐and‐price algorithm for parallel machine scheduling with time windows and job priorities

This paper presents a branch‐and‐price algorithm for scheduling n jobs on m nonhomogeneous parallel machines with multiple time windows. An additional feature of the problem is that each job falls into one of ρ priority classes and may require two operations. The objective is to maximize the weighted number of jobs scheduled, where a job in a higher priority class has “infinitely” more weight or value than a job in a lower priority class. The methodology makes use of a greedy randomized adaptive search procedure (GRASP) to find feasible solutions during implicit enumeration and a two‐cycle elimination heuristic when solving the pricing subproblems. Extensive computational results are presented based on data from an application involving the use of communications relay satellites. Many 100‐job instances that were believed to be beyond the capability of exact methods, were solved within minutes. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A mathematical formulation and efficient heuristics for the dynamic container relocation problem

The container relocation problem (CRP) is concerned with emptying a single yard‐bay which contains J containers each following a given pickup order so as to minimize the total number of relocations made during their retrieval process. The CRP can be modeled as a binary integer programming (IP) problem and is known to be NP‐hard. In this work, we focus on an extension of the CRP to the case where containers are both received and retrieved from a single yard‐bay, and call it the dynamic container relocation problem. The arrival (departure) sequences of containers to (from) the yard‐bay is assumed to be known a priori. A binary IP formulation is presented for the problem. Then, we propose three types of heuristic methods: index based heuristics, heuristics using the binary IP formulation, and a beam search heuristic. Computational experiments are performed on an extensive set of randomly generated test instances. Our results show that beam search heuristic is very efficient and performs better than the other heuristic methods.Copyright © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 101–118, 2014     

Class scheduling algorithms for Navy training schools

The problem of developing good schedules for Navy C-Schools has been modeled as a combinatorial optimization problem. The only complicating feature of the problem is that classes must be grouped together into sequences known as pipelines. An ideal schedule will have all classes in a pipeline scheduled in consecutive weeks. The objective is to eliminate the nonproductive time spent by sailors at C-Schools who are waiting for the next class in a pipeline. In this investigation an implicit enumeration procedure for this problem was developed. The key component of our algorithm is a specialized greedy algorithm which is used to obtain a good initial incumbent. Often this initial incumbent is either an optimal schedule or a near optimal schedule. In an empirical analysis with the only other competing software system, our greedy heuristic found equivalent or better solutions in substantially less computer time. This greedy heuristic was extended and modified for the A-School scheduling problem and was found to be superior to its only competitor. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 533–551, 1998     

On the asymptotic optimality of algorithms for the flow shop problem with release dates

We consider the nonpermutation flow shop problem with release dates, with the objective of minimizing the sum of the weighted completion times on the final machine. Since the problem is NP‐hard, we focus on the analysis of the performance of several approximation algorithms, all of which are related to the classical Weighted Shortest Processing Time Among Available Jobs heuristic. In particular, we perform a probabilistic analysis and prove that two online heuristics and one offline heuristic are asymptotically optimal. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

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.     

A concave‐cost production planning problem with remanufacturing options

We focus on the concave‐cost version of a production planning problem where a manufacturer can meet demand by either producing new items or by remanufacturing used items. Unprocessed used items are disposed. We show the NP‐hardness of the problem even when all the costs are stationary. Utilizing the special structure of the extreme‐point optimal solutions for the minimum concave‐cost problem with a network flow type feasible region, we develop a polynomial‐time heuristic for the problem. Our computational study indicates that the heuristic is a very efficient way to solve the problem as far as solution speed and quality are concerned. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

A selective newsvendor approach to order management

Consider a supplier offering a product to several potential demand sources, each with a unique revenue, size, and probability that it will materialize. Given a long procurement lead time, the supplier must choose the orders to pursue and the total quantity to procure prior to the selling season. We model this as a selective newsvendor problem of maximizing profits where the total (random) demand is given by the set of pursued orders. Given that the dimensionality of a mixed‐integer linear programming formulation of the problem increases exponentially with the number of potential orders, we develop both a tailored exact algorithm based on the L‐shaped method for two‐stage stochastic programming as well as a heuristic method. We also extend our solution approach to account for piecewise‐linear cost and revenue functions as well as a multiperiod setting. Extensive experimentation indicates that our exact approach rapidly finds optimal solutions with three times as many orders as a state‐of‐the‐art commercial solver. In addition, our heuristic approach provides average gaps of less than 1% for the largest problems that can be solved exactly. Observing that the gaps decrease as problem size grows, we expect the heuristic approach to work well for large problem instances. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

Optimal shift scheduling: A branch‐and‐price approach

We present a branch‐and‐price technique for optimal staff scheduling with multiple rest breaks, meal break, and break windows. We devise and implement specialized branching rules suitable for solving the set covering type formulation implicitly, using column generation. Our methodology is more widely applicable and computationally superior to the alternative methods in the literature. We tested our methodology on 365 test problems involving between 1728 and 86400 shift variations, and 20 demand patterns. In a direct comparison with an alternative method, our approach yields significant improvements both in cpu time and in the number of problem instances solved to optimality. The improvements were particularly marked for problems involving larger numbers of feasible shifts. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 185–200, 2000     

A decomposition heuristic for the twin robots scheduling problem

This article provides an efficient heuristic based on decomposition for the twin robots scheduling problem (TRSP). TRSP concerns two moving robots executing storage and retrieval requests in parallel along a shared pathway. The depots are located at both ends of the line and a dedicated robot is assigned to each of them. While moving goods between their respective depots and some storage locations on the line, noncrossing constraints among robots need to be considered. Our heuristic uses a dynamic programming framework to determine the schedule of one robot while keeping the other one's fixed. It finds near‐optimal solutions even for large problem instances with hundreds of jobs in a short time span. © 2014 Wiley Periodicals, Inc. 62:16–22, 2015     

Coordinated scheduling of customer orders for quick response

The scheduling problem addressed in this paper concerns a manufacturer who produces a variety of product types and operates in a make‐to‐order environment. Each customer order consists of known quantities of the different product types, and must be delivered as a single shipment. Periodically the manufacturer schedules the accumulated and unscheduled customer orders. Instances of this problem occur across industries in manufacturing as well as in service environments. In this paper we show that the problem of minimizing the weighted sum of customer order delivery times is unary NP‐hard. We characterize the optimal schedule, solve several special cases of the problem, derive tight lower bounds, and propose several heuristic solutions. We report the results of a set of computational experiments to evaluate the lower bounding procedures and the heuristics, and to determine optimal solutions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.