Search

We study a fundamental model of resource allocation in which a finite amount of service capacity must be allocated to a stream of jobs of different priorities arriving randomly over time. Jobs incur costs and may also cancel while waiting for service. To increase the rate of service, overtime capacity can be used at a cost. This model has application in healthcare scheduling, server applications, make-to-order manufacturing systems, general service systems, and green computing. We present an online algorithm that minimizes the total cost due to waiting, cancellations and overtime capacity usage. We prove that our scheduling algorithm has cost at most twice of an optimal offline algorithm. This competitive ratio is the best possible for this class of problems. We also provide extensive numerical experiments to test the performance of our algorithm and its variants.

We consider the problem of minimizing daily expected resource usage and overtime costs across multiple parallel resources such as anesthesiologists and operating rooms, which are used to conduct a variety of surgical procedures at large multispecialty hospitals. To address this problem, we develop a two-stage, mixed-integer stochastic dynamic programming model with recourse. The first stage allocates these resources across multiple surgeries with uncertain durations and prescribes the sequence of surgeries to these resources. The second stage determines actual start times to surgeries based on realized durations of preceding surgeries and assigns overtime to resources to ensure all surgeries are completed using the allocation and sequence determined in the first stage. We develop a data-driven robust optimization method that solves large-scale real-sized versions of this model close to optimality. We validate and implement this model as a decision support system at the UCLA Ronald Reagan Medical Center. This system effectively incorporates the flexibility in the resources and uncertainty in surgical durations, and explicitly trades off resource usage and overtime costs. This has increased the average daily utilization of the anesthesiologists by 3.5% and of the operating rooms by 3.8%. This has led to an average daily cost savings of around 7% or estimated to be $2.2 million on an annual basis. In addition, the insights based on this model have significantly influenced decision making at the operating services department at this hospital. The e-companion is available at https://doi.org/10.1287/opre.2017.1634 .

We consider an outsourcing problem where a group of manufacturers outsource jobs to a single third party who owns a specialized facility needed to process these jobs. The third party announces the time slots available on her facility, and the associated prices. Manufacturers reserve, on a first-come-first-book basis, time slots that they desire to utilize. Booking of overtime is possible, at a higher cost. A job completed after its due date incurs a tardiness cost. Each manufacturer books chunks of facility time and sequences his jobs over the time slots booked to minimize his booking, overtime, and tardiness costs. This model captures the main features of outsourcing operations in industries such as semiconductor manufacturing, biotechnology, and drug R&D. In current practice, the third party executes all outsourced jobs without performing optimization and coordination. We investigate the issue of the third party serving as a coordinator to create a win–win solution for all. We propose a model based on a cooperative game as follows: (i) Upon receiving the booking requests from the manufacturers, the third party derives an optimal solution if manufacturers cooperate, and computes the savings achieved. (ii) She devises a savings sharing scheme so that, in monetary terms, every manufacturer is better off to coordinate than to act independently or coalesce with a subgroup of manufacturers. (iii) For her work, the third party withholds a portion ρ of the booking revenue paid by the manufacturers for time slots that are released after coordination. We further design a truth-telling mechanism that can prevent any self-interested manufacturer from purposely reporting false job data to take advantage of the coordination scheme. Finally, we perform a computational experiment to assess the value of coordination to the various parties involved.

This paper addresses the problem of simultaneously determining overtime utilization and job sequencing over a finite planning horizon in a single machine job shop environment. Shipping times are assumed to occur at fixed and specified points in time, and their number is much smaller than the number of jobs. The goal is to find an overtime utilization level and job sequence that yields a “good” tradeoff between overtime cost and tardiness penalties. We begin by showing that the problem in its simplest form is NP-hard. We then present an approximate algorithm based on a capacitated transshipment formulation. This approximation provides a feasible solution along with its error bound. The algorithm is refined by incorporating the dominance relations of jobs. Extensive computational experience indicates that the algorithm is implementable in terms of both speed and accuracy.

This paper presents a mixed-integer goal programming model for expense budgeting in a hospital nursing department. The model incorporates several different objectives based upon such considerations as cost containment and providing appropriate nursing hours for delivering quality nursing care. Also considered are possible trade-offs among full-time, part-time and overtime nurses on weekdays as well as weekends. The budget includes vacation, sick leave, holiday, and seniority policies of a hospital and various constraints on a hospital nursing service imposed by nursing unions. The results are based upon data from a study hospital and indicate that the model is practical for budgeting in a hospital nursing department.

In a recent paper, Bowmar showed that the problem of balancing costs of overtime production and inventory storage to minimize the total cost of meeting given sales requirements can be set up as a transportation problem. Accordingly, he suggested the use of the Stepping Stone Method of Charnes and Cooper for the solution of this problem. The present paper discusses features of the cost matrix that lead to a simplified method of solution.

This paper develops planning-horizon theorems and algorithms for determining optimal production in period 1 when there are linear costs associated with overtime and inventory, and demand is deterministic. If overtime in each period is unrestricted and no shortages are permitted, then it is easily shown that the firm will have to know future demand for at most the next k* periods, where k* is determined by the ratio of the wage differential between overtime and regular time to the per unit holding cost per period. Using the k* concept, the paper determines planning horizons when both storage and backlogging of demand are allowed. If overtime constraints are imposed, a planning algorithm is proposed that requires less information on future demand than a linear programming model. Economic implications of this approach for decision-making and information processing in firms are discussed.

This paper seeks here a minimum cost production plan over a finite number of time periods. There is a known demand requirement (stated in production hours) to be met in each period from current and previous hours of production (stored as inventory). A production policy consists of scheduled amounts of hours, some of which are costed at regular-time wage rates, the remainder costed at overtime rates. Expansion or contraction of the work force (stated in production hours) is charged against the period-to-period variations in regular-time employment. The fluctuations in overtime production do not incur such hiring and firing costs. The amount of overtime used, however, is constrained not to exceed a specified fraction of regular-time utilized in any period. We describe algorithms for rinding an optimal policy under the assumption that all costs are described by linear functions and where demands are either monotonic increasing or decreasing in time. In addition to presenting the algorithms, we also examine certain planning horizon results implied by these algorithms. Specifically, we ascertain when optimal first period decisions can be made without knowing the precise values of all future demands and costs.