Reformulating linear programs with transportation constraints—With applications to workforce scheduling

We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multistage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more desirable since it has fewer variables and can be solved faster. We apply these ideas to reformulate two well‐known workforce staffing and scheduling problems: the shift scheduling problem and the tour scheduling problem. We also present computational results. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Optimal staffing in nonstationary service centers with constraints

This paper considers optimal staffing in service centers. We construct models for profit and cost centers using dynamic rate queues. To allow for practical optimal controls, we approximate the queueing process using a Gaussian random variable with equal mean and variance. We then appeal to the Pontryagin's maximum principle to derive a closed form square root staffing (SRS) rule for optimal staffing. Unlike most traditional SRS formulas, the main parameter in our formula is not the probability of delay but rather a cost‐to‐benefit ratio that depends on the shadow price. We show that the delay experienced by customers can be interpreted in terms of this ratio. Throughout the article, we provide theoretical support of our analysis and conduct extensive numerical experiments to reinforce our findings. To this end, various scenarios are considered to evaluate the change in the staffing levels as the cost‐to‐benefit ratio changes. We also assess the change in the service grade and the effects of a service‐level agreement constraint. Our analysis indicates that the variation in the ratio of customer abandonment over service rate particularly influences staffing levels and can lead to drastically different policies between profit and cost service centers. Our main contribution is the introduction of new analysis and managerial insights into the nonstationary optimal staffing of service centers, especially when the objective is to maximize profitability. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 615–630, 2017     

Static and dynamic scheduling of customer arrivals to a single-server system

In this article we consider a single-server system whose customers arrive by appointments only. Both static and dynamic scheduling problems are studied. In static scheduling problems, one considers scheduling a finite number of customer arrivals, assuming there is no scheduled customer arrival to the system. In dynamic scheduling problems, one considers scheduling one customer arrival only, assuming that there are a number of scheduled customers already. The expected delay time is recursively computed in terms of customer interarrival times for both cases. The objective is to minimize the weighted customer delay time and the server completion time. The problem is formulated as a set of nonlinear equations. Various numerical examples are illustrated. © 1993 John Wiley & Sons, Inc.     

Service design at diagnostic service centers

We study a service design problem in diagnostic service centers, call centers that provide medical advice to patients over the phone about what the appropriate course of action is, based on the caller's symptoms. Due to the tension between increased diagnostic accuracy and the increase in waiting times more in‐depth service requires, managers face a difficult decision in determining the optimal service depth to guide the diagnostic process. The specific problem we consider models the situation when the capacity (staffing level) at the center is fixed, and when the callers have both congestion‐ and noncongestion‐related costs relating to their call. We develop a queueing model incorporating these features and find that the optimal service depth can take one of two different structures, depending on factors such as the nurses' skill level and the maximum potential demand. Sensitivity analyses of the two optimal structures show that they are quite different. In some situations, it may (or may not) be optimal for the manager to try to expand the demand at the center, and increasing skill level may (or may not) increase congestion. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Facility location models for immobile servers with stochastic demand

This paper presents several models for the location of facilities subject to congestion. Motivated by applications to locating servers in communication networks and automatic teller machines in bank systems, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. We consider this problem from three different perspectives, that of (i) the service provider (wishing to limit costs of setup and operating servers), (ii) the customers (wishing to limit costs of accessing and waiting for service), and (iii) both the service provider and the customers combined. In all cases, a minimum level of service quality is ensured by imposing an upper bound on the server utilization rate at a service facility. The latter two perspectives also incorporate queueing delay costs as part of the objective. Some cases are amenable to an optimal solution. For those cases that are more challenging, we either propose heuristic procedures to find good solutions or establish equivalence to other well‐studied facility location problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

An efficient metaheuristic for integrated scheduling and staffing IT projects based on a generalized minimum cost flow network

Scheduling IT projects and assigning the project work to human resources are an important and common tasks in almost any IT service company. It is particularly complex because human resources usually have multiple skills. Up to now only little work has considered IT‐specific properties of the project structure and human resources. In this article, we present an optimization model that simultaneously schedules the activities of multiple IT projects with serial network structures and assigns the project work to multiskilled internal and external human resources with different efficiencies. The goal is to minimize costs. We introduce a metaheuristic that decomposes the problem into a binary scheduling problem and a continuous staffing problem where the latter is solved efficiently by exploiting its underlying network structure. For comparison, we solve the mixed–binary linear program with a state–of–the–art commercial solver. The impacts of problem parameters on computation time and solution gaps between the metaheuristic and the solver are assessed in an experimental study. Our results show that the metaheuristic provides very favorable results in considerable less time than the solver for midsize problems. For larger problems, it shows a similar performance while the solver fails to return feasible solutions. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 111–127, 2012     

Sequencing with setup time and order tardiness trade-offs

We consider the problem of scheduling customer orders on a single facility where each order consists of several jobs that can be clustered into several groups. When a facility is changed over to another group, a setup time associated with the new group is required. Two particular problems are considered in this context. One is to consider the total setup time and the number of tardy orders jointly. The other is to consider the total setup time and the maximum tardiness jointly. The total setup time in both problems represents a measure of internal efficiency, whereas the number of tardy orders and the maximum tardiness represent a measure of external efficiency. In any shop, the decision maker must consider the tradeoffs between large setup costs associated with a more frequent changeover schedule versus the cost of tardy orders that might be induced by a less-frequent changeover schedule. In this article branch-and-bound algorithms are proposed to identify the set of nondominated schedules for the two bicriteria problems. © 1996 John Wiley & Sons, Inc.     

An integer programming model for the weekly tour scheduling problem

We study a workforce planning and scheduling problem in which weekly tours of agents must be designed. Our motivation for this study comes from a call center application where agents serve customers in response to incoming phone calls. Similar to many other applications in the services industry, the demand for service in call centers varies significantly within a day and among days of the week. In our model, a weekly tour of an agent consists of five daily shifts and two days off, where daily shifts within a tour may be different from each other. The starting times of any two consecutive shifts, however, may not differ by more than a specified bound. Furthermore, a tour must also satisfy constraints regarding the days off, for example, it may be required that one of the days off is on a weekend day. The objective is to determine a collection of weekly tours that satisfy the demand for agents' services, while minimizing the total labor cost of the workforce. We describe an integer programming model where a weekly tour is obtained by combining seven daily shift scheduling models and days‐off constraints in a network flow framework. The model is flexible and can accommodate different daily models with varying levels of detail. It readily handles different days‐off rules and constraints regarding start time differentials in consecutive days. Computational results are also presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 607–624, 2001.     

Production and transport logistics scheduling with two transport mode choices

This paper considers a new class of scheduling problems arising in logistics systems in which two different transportation modes are available at the stage of product delivery. The mode with the shorter transportation time charges a higher cost. Each job ordered by the customer is first processed in the manufacturing facility and then transported to the customer. There is a due date for each job to arrive to the customer. Our approach integrates the machine scheduling problem in the manufacturing stage with the transportation mode selection problem in the delivery stage to achieve the global maximum benefit. In addition to studying the NP‐hard special case in which no tardy job is allowed, we consider in detail the problem when minimizing the sum of the total transportation cost and the total weighted tardiness cost is the objective. We provide a branch and bound algorithm with two different lower bounds. The effectiveness of the two lower bounds is discussed and compared. We also provide a mathematical model that is solvable by CPLEX. Computational results show that our branch and bound algorithm is more efficient than CPLEX. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Scheduling policies for an antiterrorist surveillance system

This article concerns scheduling policies in a surveillance system aimed at detecting a terrorist attack in time. Terrorist suspects arriving at a public area are subject to continuous monitoring, while a surveillance team takes their biometric signatures and compares them with records stored in a terrorist database. Because the surveillance team can screen only one terrorist suspect at a time, the team faces a dynamic scheduling problem among the suspects. We build a model consisting of an M/G/1 queue with two types of customers—red and white—to study this problem. Both types of customers are impatient but the reneging time distributions are different. The server only receives a reward by serving a red customer and can use the time a customer has spent in the queue to deduce its likely type. In a few special cases, a simple service rule—such as first‐come‐first‐serve—is optimal. We explain why the problem is in general difficult and we develop a heuristic policy motivated by the fact that terrorist attacks tend to be rare events. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Service levels in distribution systems with random customer order size

An approximate method for measuring the service levels of the warehouse-retailer system operating under (s, S) policy is presented. All the retailers are identical and the demand process at each retailer follows a stationary stuttering Poisson process. This type of demand process allows customer orders to be for a random number of units, which gives rise to the undershoot quantity at both the warehouse and retailer levels. Exact analyses of the distribution of the undershoot quantity and the number of orders place by a retailer during the warehouse reordering lead time are derived. By using this distribution together with probability approximation and other heuristic approaches, we model the behavior of the warehouse level. Based on the results of the warehouse level and on an existing framework from previous work, the service level at the retailer level is estimated. Results of the approximate method are then compared with those of simulation. © 1995 John Wiley & Sons, Inc.     

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.     

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     

基于行为约束的军事信息服务描述及过滤方法

针对传统服务描述模型无法对军事信息服务中服务的使用权限、适用范围等非功能约束信息进行全面、标准化描述的问题,扩展已有web服务通用描述模型,提出了一种基于行为约束的军事信息服务描述模型,以全面支持军事信息服务功能、行为约束和服务质量的描述.在此基础上采用分层匹配思想,在服务发现过程中引入相似度和匹配算法,对行为约束的相...     

Optimal dynamic rules for assigning customers to servers in a heterogeneous queuing system

We consider a queuing system in which both customers and servers may be of several types. The distribution of a customer's service time is assumed to depend on both the customer's type and the type of server to which he is assigned. For a model with two servers and two customer types, conditions are presented which ensure that the discounted number of service completions is maximized by assigning customers with longer service times to faster servers. Generalizations to more complex models are discussed.     

Probabilistic a priori routing-location problems

In many routing-location models customers located at nodes of a network generate calls for service with known probabilities. The customers that request service in a particular day are served by a single server that performs a service tour visiting these customers. The order of providing service to customers for each potential list of calls is uniquely defined by some a priori fixed basic sequence of all the customers (a priori tour). The problems addressed in this article are to find an optimal home location or an optimal basic sequence for the server so as to minimize the expectation of a criterion. The following criteria are considered: the total waiting time of all the customers, the total length of the tour, the maximal waiting time of a customer, the average traveled length per customer, and the average waiting time per customer. We present polynomial-time algorithms for the location problems. For the routing problems we present lower bounds that can be calculated efficiently (in polynomial time) and used in a branch-and-bound scheme. © 1994 John Wiley & Sons, Inc.     

Bayesian analysis of queues with impatient customers: Applications to call centers

Queuing models have been extensively used in the literature for obtaining performance measures and developing staffing policies. However, most of this work has been from a pure probabilistic point of view and has not addressed issues of statistical inference. In this article, we consider Bayesian queuing models with impatient customers with particular emphasis on call center operations and discuss further extensions. We develop the details of Bayesian inference for queues with abandonment such as the M/M/s + M model (Erlang‐A). In doing so, we discuss the estimation of operating characteristics and its implications on staffing. We illustrate the implementation of the Bayesian models using actual arrival, service, and abandonment data from call centers. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

The customer order lead-time problem on parallel machines

We consider the problem of scheduling customer orders, each consisting of one or more individual jobs, on a set of parallel processors with the objective of minimizing average order completion time. We provide simple intuitive heuristics to guide managers in this environment and introduce lower bounds that show that these heuristics are effective for a wide variety of problems. © 1996 John Wiley & Sons, Inc.     

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