Optimal control of continuous-time terminal-value birth-and-death processes and airline overbooking

Consider a continuous-time airline overbooking problem that relates to a single-leg flight and a single service class with a stationary fare. Passengers may cancel their reservations at any time and receive a full refund. Therefore fares can be thought of as being paid at flight time. At that time, the airline bumps passengers in excess of flight capacity and pays a penalty for so doing. The wflight-time revenue, that is, fares received less bumping penalties paid, is quasiconcave in the number of reservations at that time. We model the reservations process as a continuous-time terminal-value birth-and-death process. A more general model than is necessary for an airline reservations system is considered, in which the airline controls both the reservation acceptance (birth) and the cancellation (death) rates. In current practice airlines do not control cancellation rates (though other industries do exercise such control, e.g., hotels) and control reservation acceptance rates by declining reservation requests. The more general model might be applied to other targeting applications, such as steering a vehicle through space toward a target location. For the general model a piecewise-constant booking-limit policy is optimal; that is, at all times the airline accepts reservation requests up to a booking limit if the current number of reservations is less than that booking limit, and declines reservation requests otherwise. When the airline is allowed to decline all reservation requests, as is the case in practice, the booking-limit optimal policy defined by using the greatest optimal booking limit at all times is piecewise constant. Moreover, these booking limits fall toward flight time. © 1996 John Wiley & Sons, Inc.     

Scheduling to minimize release-time resource consumption and tardiness penalties

We consider the problem of scheduling a set of jobs with a common due-date on a single-machine where the release time of a job is related to the amount of resource consumed. The objective is to minimize the total resource consumption and the total tardiness. While the problem is strongly NP-hard in general, we discuss two different special cases for which special properties are identified and used to develop efficient pseudo-polynomial time algorithms. © 1995 John Wiley & Sons, Inc.     

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.     

Stochastic production capacity: A bane or a boon for quick response supply chains?

The quick response (QR) system that can cope with demand volatility by shortening lead time has been well studied in the literature. Much of the existing literature assumes implicitly or explicitly that the manufacturers under QR can always meet the demand because the production capacity is always sufficient. However, when the order comes with a short lead time under QR, availability of the manufacturer's production capacity is not guaranteed. This motivates us to explore QR in supply chains with stochastic production capacity. Specifically, we study QR in a two-echelon supply chain with Bayesian demand information updating. We consider the situation where the manufacturer's production capacity under QR is uncertain. We first explore how stochastic production capacity affects supply chain decisions and QR implementation. We then incorporate the manufacturer's ability to expand capacity into the model. We explore how the manufacturer determines the optimal capacity expansion decision, and the value of such an ability to the supply chain and its agents. Finally, we extend the model to the two-stage two-ordering case and derive the optimal ordering policy by dynamic programming. We compare the single-ordering and two-ordering cases to generate additional managerial insights about how ordering flexibility affects QR when production capacity is stochastic. We also explore the transparent supply chain and find that our main results still hold.     

From the sea to outer space: The command of space as the foundation of spacepower theory

Colin Gray once lamented the absence of a ‘Mahan for the final frontier’ and spacepower theory in strategic studies. This article proposes the command of space as the fundamental concept of spacepower theory, and that Mahan himself has much to offer in the endeavour of spacepower theory-making than has hitherto been realised. The theory is advanced by tempering versions of the ‘command of space’, stressing its educational intent, and explaining the nuanced sub-concepts of space control and denial through understanding some precedents set by seapower theory. In the process, aspects of Mahanian and Corbettian seapower theory are unified.     

The two-machine permutation flow shop with state-dependent processing times

If the processing time of each job in a flow shop also depends on the time spent prior to processing, then the choice of a sequence influences processing times. This nonstandard scheduling problem is studied here for the minimum makespan schedule in a flow shop with two machines. The problem is NP-hard in the strong sense and already contains the main features of the general case [10]. Restricting to the case of permutation schedules, we first determine the optimal release times of the jobs for a given sequence. Permutation schedules are evaluated for this optimal policy, and the scheduling problem is solved using branch-and-bound techniques. We also show the surprising result that the optimal schedule may not be a permutation schedule. Numerical results on randomly generated data are provided for permutation schedules. Our numerical results confirm our preliminary study [10] that fairly good approximate solutions can efficiently be obtained in the case of limited computing time using the heuristics due to Gilmore and Gomory [7]. © 1993 John Wiley & Sons, Inc.     

A new heuristic solution method in resource-constrained project scheduling

A new heuristic method is presented for the resolution of multiresource constrained conflicts in project scheduling. In attempting to find a minimal makespan solution, the algorithm employs a simple procedure to generate a feasible solution with no backtracking. A postanalysis phase then applies a hill-climbing search. The solution method is different from existing heuristic methods in that it repairs resource conflicts rather than constructs detailed schedules by dispatching activities. Resource-violating sets of activities are identified which must be prevented from concurrent execution because this would violate resource constraints. Repairs are made by imposing an arc to sequence two activities in such a resource violating set. Computational results are compared with those of existing heuristics for the minimal makespan problem.     

Order-statistic calculation,costs, and service in an (s,Q) inventory system

A retailer or distributor of finished goods, or the manager of a spare-parts inventory system, must generally forecast the major portion of demand. A specific customer-service level p (fraction of replenishment intervals with no stockout) implies two challenges: achieve the service within a small interval plus or minus, and do so with a minimum-cost investment in inventory. The pth fractile of lead-time demand (LTD) is the reorder point (ROP) for this service measure, and is often approximated by that fractile of a normal distribution. With this procedure, it is easy to set safety stocks for an (s, Q) inventory system. However, Bookbinder and Lordahl [2] and others have identified cases where the normal approximation yields excessive costs and/or lower service than desired. This article employs an order-statistic approach. Using available LTD data, the ROP is simply estimated from one or two of the larger values in the sample. This approach is sufficiently automatic and intuitive for routine implementation in industry, yet is distribution free. The order-statistic method requires only a small amount of LTD data, and makes no assumptions on the form of the underlying LTD distribution, nor even its parameters μ and ρ. We compare the order-statistic approach and the normal approximation, first in terms of customer service and then using a model of expected annual cost. Based upon characteristics of the available LTD data, we suggest a procedure to aid a practitioner in choosine between the normal and order-statistic method. © 1994 John Wiley & Sons, Inc.     

Optimizing the allocation of components to kits in small-lot,multiechelon assembly systems

The kitting problem in multiechelon assembly systems is to allocate on-hand stock and anticipated future deliveries to kits so that cost is minimized. This article structures the kitting problem and describes several preprocessing methods that are effective in refining the formulation. The model is resolved using an optimizing approach based on Lagrangian relaxation, which yields a separable problem that decomposes into a subproblem for each job. The resulting subproblems are resolved using a specialized dynamic programming algorithm, and computational efficiency is enhanced by dominance properties devised for that purpose. The Lagrangian problem is resolved effectively using subgradient optimization and a specialized branching method incorporated in the branch-and-bound procedure. Computational experience demonstrates that the specialized approach outperforms the general-purpose optimizer OSL. The new solution approach facilitates time-managed flow control, prescribing kitting decisions that promote cost-effective performance to schedule. © 1994 John Wiley & Sons. Inc.