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.     

Community preferences,insurgency, and the success of reconstruction spending

Existing theory on counterinsurgency does not adequately explain persistent insurrection in face of the reconstruction work currently underway in Afghanistan and Iraq. We starkly depart from the literature by developing a simple model of reconstruction allowing misalignment of occupier spending with community preferences. Insurgency arises endogenously as a result of the mix of spending rather than its level. Occupier insistence on its preferred path of reconstruction may lead to fewer projects of any kind being completed. In equilibrium, the occupier may accept an endogenous insurgency to achieve a preferred project mix, or be constrained in its choice even when no insurgency occurs.     

Makespan minimization in the two‐machine flowshop batch scheduling problem

In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part‐types are to be produced in a flexible manufacturing cell organized into a two‐stage production line. The jobs are processed in batches on the first machine, and the completion time of a job is defined as the completion time of the batch containing it. When processing of all jobs in a batch is completed on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch processing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batches so that the makespan is minimized. The problem is shown to be strongly NP‐hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approximate solutions. We conduct computational experiments to study the effectiveness of the proposed heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 128–144, 2000     

Heuristics for the multi‐resource generalized assignment problem

The well‐known generalized assignment problem (GAP) involves the identification of a minimum‐cost assignment of tasks to agents when each agent is constrained by a resource in limited supply. The multi‐resource generalized assignment problem (MRGAP) is the generalization of the GAP in which there are a number of different potentially constraining resources associated with each agent. This paper explores heuristic procedures for the MRGAP. We first define a three‐phase heuristic which seeks to construct a feasible solution to MRGAP and then systematically attempts to improve the solution. We then propose a modification of the heuristic for the MRGAP defined previously by Gavish and Pirkul. The third procedure is a hybrid heuristic that combines the first two heuristics, thus capturing their relative strengths. We discuss extensive computational experience with the heuristics. The hybrid procedure is seen to be extremely effective in solving MRGAPs, generating feasible solutions to more than 99% of the test problems and consistently producing near‐optimal solutions. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 468–483, 2001     

An application of the MTP2 property on bounds on system reliability

This paper is concerned with the joint prior distribution of the dependent reliabilities of the components of a binary system. When this distribution is MTP₂ (Multivariate Totally Positive of Order 2), it is shown in general that this actually makes the machinery of Natvig and Eide [7] available to arrive at the posterior distribution of the system's reliability, based on data both at the component and system level. As an illustration in a common environmental stress case, the joint prior distribution of the reliabilities is shown to have the MTP₂ property. We also show, similarly to Gåsemyr and Natvig [3], for the case of independent components given component reliabilities how this joint prior distribution may be based on the combination of expert opinions. A specific system is finally treated numerically. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 741–755, 1997     

The equivalence of general set-covering and implicit integer programming formulations for shift scheduling

In a recent article we demonstrated that implicit optimal modeling for shift scheduling (P2) has inherent size and execution time advantages over the general set-covering formulation for shift scheduling (P1) [11, 13]. We postulated that the absence of extraordinary overlap (EO) was a requirement for the equivalence of P1 and P2. We have defined EO as the condition in which the earliest and latest starts for a break in one shift are earlier and later than the earliest and latest starts for a break in any other shift(s). In this article, we prove that our earlier postulate was accurate. Additionally, we discuss research extensions and note other scheduling problems for which implicit modeling may be appropriate. © 1996 John Wiley & Sons, Inc.     

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.