Distributionally robust maximum probability shortest path problem

In this study, we discuss and develop a distributionally robust joint chance-constrained optimization model and apply it for the shortest path problem under resource uncertainty. In sch a case, robust chance constraints are approximated by constraints that can be reformulated using convex programming. Since the issue we are discussing here is of the multi-resource type, the resource related to cost is deterministic; however, we consider a robust set for other resources where covariance and mean are known. Thus, the chance-constrained problem can be expressed in terms of a cone constraint. In addition, since our problem is joint chance-constrained optimization, we can use Bonferroni approximation to divide the problem into L separate problems in order to build convex approximations of distributionally robust joint chance constraints. Finally, numerical results are presented to illustrate the rigidity of the bounds and the value of the distributionally robust approach.

     

Optimizing the Staffing and Routing of Small‐Size Hierarchical Call Centers

Multiple‐skill call centers propagate rapidly with the development of telecommunications. An abundance of literature has already been published on call centers. Here, we want to focus on centers that would typically occur in business‐to‐business environments; these are call centers that handle many types of calls but where the arrival rate for each type is low. To find an optimal configuration, the integrality of the decision variables is a much more important issue than for larger call centers. The present paper proposes an approach that uses elements of combinatorial optimization to find optimal configurations. We develop an approximation method for the evaluation of the service performance. Next, we search for the minimum‐cost configuration subject to service‐level constraints using a branch‐and‐bound algorithm. What is at stake is to find the right balance between gains resulting from the economies of scale of pooling and the higher cost or cross‐trained agents. The article shows that in most cases this method significantly decreases the staffing cost compared with configurations with only cross‐trained or dedicated operators.     

Value-Based Routing and Preference-Based Routing in Customer Contact Centers

Telephone call centers and their generalizations—customer contact centers—usually handle several types of customer service requests (calls). Since customer service representatives (agents) have different call-handling abilities and are typically cross-trained in multiple skills, contact centers exploit skill-based routing (SBR) to assign calls to appropriate agents, aiming to respond properly as well as promptly. Established agent-staffing and SBR algorithms ensure that agents have the required call-handling skills and that call routing is performed so that constraints are met for standard congestion measures, such as the percentage of calls of each type that abandon before starting service and the percentage of answered calls of each type that are delayed more than a specified number of seconds. We propose going beyond traditional congestion measures to focus on the expected value derived from having particular agents handle various calls. Expected value might represent expected revenue or the likelihood of first-call resolution. Value might also reflect agent call-handling preferences. We show how value-based routing (VBR) and preference-based routing (PBR) can be introduced in the context of an existing SBR framework, based on static-priority routing using a highly-structured priority matrix, so that constraints are still met for standard congestion measures. Since an existing SBR framework is used to implement VBR and PBR, it is not necessary to replace the automatic call distributor (ACD). We show how mathematical programming can be used, with established staffing requirements, to find a desirable priority matrix. We select the priority matrix to use during a specified time interval (e.g., 30-minute period) by maximizing the total expected value over that time interval, subject to staffing constraints.     

Staffing and scheduling flexible call centers by two-stage robust optimization

We study the shift scheduling problem in a multi-shift, flexible call center. Differently from previous approaches, the staffing levels ensuring the desired quality of service are considered uncertain, leading to a two-stage robust integer program with right-hand-side uncertainty. We show that, in our setting, modeling the correlation of the demands in consecutive time slots is easier than in other staffing approaches. The complexity issues of a Benders type reformulation are investigated and a branch-and-cut algorithm is devised. The approach can efficiently solve real-world problems from an Italian call center and effectively support managers decisions. In fact, we show that robust shifts have very similar costs to those evaluated by the traditional (deterministic) method while ensuring a higher level of protection against uncertainty.     

Staffing Call Centers with Uncertain Arrival Rates and Co‐sourcing

In a call center, staffing decisions must be made before the call arrival rate is known with certainty. Once the arrival rate becomes known, the call center may be over‐staffed, in which case staff are being paid to be idle, or under‐staffed, in which case many callers hang‐up in the face of long wait times. Firms that have chosen to keep their call center operations in‐house can mitigate this problem by co‐sourcing; that is, by sometimes outsourcing calls. Then, the required staffing N depends on how the firm chooses which calls to outsource in real time, after the arrival rate realizes and the call center operates as a M/M/N + M queue with an outsourcing option. Our objective is to find a joint policy for staffing and call outsourcing that minimizes the long‐run average cost of this two‐stage stochastic program when there is a linear staffing cost per unit time and linear costs associated with abandonments and outsourcing. We propose a policy that uses a square‐root safety staffing rule, and outsources calls in accordance with a threshold rule that characterizes when the system is “too crowded.” Analytically, we establish that our proposed policy is asymptotically optimal, as the mean arrival rate becomes large, when the level of uncertainty in the arrival rate is of the same order as the inherent system fluctuations in the number of waiting customers for a known arrival rate. Through an extensive numerical study, we establish that our policy is extremely robust. In particular, our policy performs remarkably well over a wide range of parameters, and far beyond where it is proved to be asymptotically optimal.     

A Dynamic Disaggregation Approach to Approximate Linear Programs for Network Revenue Management

The linear programming approach to approximate dynamic programming has received considerable attention in the recent network revenue management (RM) literature. A major challenge of the approach lies in solving the resulting approximate linear programs (ALPs), which often have a huge number of constraints and/or variables. Starting from a recently developed compact affine ALP for network RM, we develop a novel dynamic disaggregation algorithm to solve the problem, which combines column and constraint generation and exploits the structure of the underlying problem. We show that the formulation can be further tightened by considering structural properties satisfied by an optimal solution. We prove that the sum of dynamic bid‐prices across resources is concave over time. We also give a counterexample to demonstrate that the dynamic bid‐prices of individual resources are not concave in general. Numerical experiments demonstrate that dynamic disaggregation is often orders of magnitude faster than existing algorithms in the literature for problem instances with and without choice. In addition, adding the concavity constraints can further speed up the algorithm, often by an order of magnitude, for problem instances with choice.     

Some graph optimization problems with weights satisfying linear constraints

In this paper, we study several graph optimization problems in which the weights of vertices or edges are variables determined by several linear constraints, including maximum matching problem under linear constraints (max-MLC), minimum perfect matching problem under linear constraints (min-PMLC), shortest path problem under linear constraints (SPLC) and vertex cover problem under linear constraints (VCLC). The objective of these problems is to decide the weights that are feasible to the linear constraints, and find the optimal solutions of corresponding graph optimization problems among all feasible choices of weights. We find that these problems are NP-hard and are hard to be approximated in general. These findings suggest us to explore various special cases of them. In particular, we show that when the number of constraints is a fixed constant, all these problems are polynomially solvable. Moreover, if the total number of distinct weights is a fixed constant, then max-MLC, min-PMLC and SPLC are polynomially solvable, and VCLC has a 2-approximation algorithm. In addition, we propose approximation algorithms for various cases of max-MLC.

     

The falling tide algorithm: A new multi-objective approach for complex workforce scheduling

We present a hybrid approach of goal programming and meta-heuristic search to find compromise solutions for a difficult employee scheduling problem, i.e. nurse rostering with many hard and soft constraints. By employing a goal programming model with different parameter settings in its objective function, we can easily obtain a coarse solution where only the system constraints (i.e. hard constraints) are satisfied and an ideal objective-value vector where each single goal (i.e. each soft constraint) reaches its optimal value. The coarse solution is generally unusable in practise, but it can act as an initial point for the subsequent meta-heuristic search to speed up the convergence. Also, the ideal objective-value vector is, of course, usually unachievable, but it can help a multi-criteria search method (i.e. compromise programming) to evaluate the fitness of obtained solutions more efficiently. By incorporating three distance metrics with changing weight vectors, we propose a new time-predefined meta-heuristic approach, which we call the falling tide algorithm, and apply it under a multi-objective framework to find various compromise solutions. By this approach, not only can we achieve a trade off between the computational time and the solution quality, but also we can achieve a trade off between the conflicting objectives to enable better decision-making.     

AN IMPROVED HEURISTIC FOR STAFFING TELEPHONE CALL CENTERS WITH LIMITED OPERATING HOURS

Many telephone call centers that experience cyclic and random customer demand adjust their staffing over the day in an attempt to provide a consistent target level of customer service. The standard and widely used staffing method, which we call the stationary independent period by period (SIPP) approach, divides the workday into planning periods and uses a series of stationary independent Erlang‐c queuing models—one for each planning period—to estimate minimum staffing needs. Our research evaluates and improves upon this commonly used heuristic for those telephone call centers with limited hours of operation during the workday. We show that the SIPP approach often suggests staffing that is substantially too low to achieve the targeted customer service levels (probability of customer delay) during critical periods. The major reasons for SIPP‘ s shortfall are as follows: (1) SIPP's failure to account for the time lag between the peak in customer demand and when system congestion actually peaks; and (2) SIPP’ s use of the planning period average arrival rate, thereby assuming that the arrival rate is constant during the period. We identify specific domains for which SIPP tends to suggest inadequate staffing. Based on an analysis of the factors that influence the magnitude of the lag in infinite server systems that start empty and idle, we propose and test two simple “lagged” SIPP modifications that, in most situations, consistently achieve the service target with only modest increases in staffing.     

Constraint-based model for the cyclic multi-hoists scheduling problem

This article presents a method for the resolution of a material handling scheduling problem. The case studied is a real industrial problem. It consists of finding a cyclic schedule for hoist movements in a treatment surface shop. In this kind of facility, several hoists are used for all the handling operations and they have to share common zones. Then it is necessary to control that there is no collision. The mathematical formulation of the problem is based on a combination of disjunctive constraints. The constraints describe either movement schedule or collision avoidance. The resolution procedure presented identifies all the collision configurations and then uses a branch and bound-like algorithm to find the optimal solution of a given problem. The language chosen for our implementation is the constraint logic programming language: Prolog IV, which is able to solve constraints with rational variables. It actively uses the constraint propagation mechanism that can be found in several languages.     

Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios

We consider the design of a multicommodity flow network, in which point-to-point demands are routed across the network subject to link capacity restrictions. Such a design must build enough capacity and diverse routing paths through the network to ensure that feasible multicommodity flows continue to exist, even when components of the network fail. In this paper, we examine several methodologies to optimally design a minimum-cost survivable network that continues to support a multicommodity flow under any of a given set of failure scenarios, where each failure scenario consists of the simultaneous failure of multiple arcs. We begin by providing a single extensive form mixed-integer programming formulation for this problem, along with a Benders decomposition algorithm as an alternative to the extensive form approach. We next investigate strategies to improve the performance of the algorithm by augmenting the master problem with several valid inequalities such as cover constraints, connectivity constraints, and path constraints. For the smallest instances (eight nodes, 10 origin–destination pairs, and 10 failure scenarios), the Benders implementation consumes only 10% of the time required by the mixed-integer programming formulation, and our best augmentation strategy reduces the solution time by another 50%. For medium- and large-sized instances, the extensive form problem fails to terminate within 2 h on any instance, while our decomposition algorithms provide optimal solutions on all but two problem instances.     

Keeping partners together: algorithmic results for the hospitals/residents problem with couples

The Hospitals/Residents problem with Couples (HRC) is a generalisation of the classical Hospitals/Residents problem (HR) that is important in practical applications because it models the case where couples submit joint preference lists over pairs of hospitals (h _i ,h _j ). We consider a natural restriction of HRC in which the members of a couple have individual preference lists over hospitals, and the joint preference list of the couple is consistent with these individual lists in a precise sense. We give an appropriate stability definition and show that, in this context, the problem of deciding whether a stable matching exists is NP-complete, even if each resident’s preference list has length at most 3 and each hospital has capacity at most 2. However, with respect to classical (Gale-Shapley) stability, we give a linear-time algorithm to find a stable matching or report that none exists, regardless of the preference list lengths or the hospital capacities. Finally, for an alternative formulation of our restriction of HRC, which we call the Hospitals/Residents problem with Sizes (HRS), we give a linear-time algorithm that always finds a stable matching for the case that hospital preference lists are of length at most 2, and where hospital capacities can be arbitrary.     

震后应急物资配送的模糊定位-路径问题研究

从系统集成优化的角度研究震后应急物资配送的一种新模糊定位-路径问题(LRP),综合考虑救灾点所在地理位置和地形导致的应急车辆行驶时间的随机性、救灾点应急物资需求量的不确定性与应急物资配送的时间紧迫性,以应急物资总运达时间最短与总配送成本最小为目标,构建一个基于机会约束规划的多目标模糊LRP优化模型,并根据模型的特点设计了一种混合免疫遗传算法予以求解。最后,通过算例验证了本文方法能有效解决震后应急物资配送的模糊多目标LRP,实现了震后应急物流中心定位和应急车辆路径规划的联合决策。     

Practical scheduling for call center operations

A practical spreadsheet-based scheduling method is developed to determine the optimal allocation of service agents to candidate tour types and start times in an inbound call center. A stationary Markovian queueing model with customer abandonment is employed to determine required staffing levels for a sequence of time intervals with varying call volumes, handling times, and relative agent availabilities. These staffing requirements populate a quadratic programming model for determining the distribution of agent tours that will maximize the fraction of offered calls beginning service within a target response time, subject to side constraints on tour type quantities. The optimal distribution is scaled to reflect the total number of scheduled agents, and a near-optimal integer solution is derived using rounding thresholds found by successive one-dimensional searches. This novel approach has been successfully implemented in large service centers at Qwest Communications and could easily be adapted to other operational environments.     

Eco-friendly container transshipment route scheduling problem with repacking operations

Currently, a huge amount of cargo is transported via containers by liner shipping companies. Under stochastic demand, repacking operations and carbon reduction, which may lead to an increase in effectiveness and environmental improvement, have been rarely considered in previous literature. In this paper, we investigate a container transshipment route scheduling problem with repacking operations under stochastic demand and environmental protection. The problem is a combinatorial optimization problem. Lacking historical data, a chance-constrained programming model is proposed to minimize the total operating and environment-related costs. We choose two distribution-free approaches, i.e., approximation based in Markov’s Inequality and Mixed Integer Second-Order Conic Program to approximate the chance constraints. As the loses induced by unfulfilled demand are not taken into account in the above model, a scenario-based model is developed considering the loses. Risk-neutral model may provide solutions that perform poorly while considering uncertainty. To incorporate decision makers’ perspectives, therefore, we also propose a risk-averse model adopting a risk aversion measure called Conditional Value-at-Risk to meet different preferences. Finally, we conduct computational experiments based on real data to compare the performances of the modeling methods and illustrate the impacts by testing different risk levels and confidence levels.

     

An access network design problem with end-to-end QoS constraints

In this paper, we present an access network design problem with end-to-end quality of service (QoS) requirement. The problem can be conceptualized as a two-level hierarchical location-allocation problem on the tree topology with nonlinear side constraints. The objective function of the nonlinear mixed integer programming model minimizes the total cost of switch and fiber cable, while satisfying demand within the prescribed level of QoS. By exploiting the inherent structure of the nonlinear QoS constraints, we develop linearization techniques for finding an optimal solution. Also, we devise an effective exact optimal algorithm within the context of disjunctive constraint generation. We present promising computational results that demonstrate the effectiveness of the proposed solution procedure.     

Exact solution method to solve large scale integer quadratic multidimensional knapsack problems

In this paper we develop a branch-and-bound algorithm for solving a particular integer quadratic multi-knapsack problem. The problem we study is defined as the maximization of a concave separable quadratic objective function over a convex set of linear constraints and bounded integer variables. Our exact solution method is based on the computation of an upper bound and also includes pre-procedure techniques in order to reduce the problem size before starting the branch-and-bound process. We lead a numerical comparison between our method and three other existing algorithms. The approach we propose outperforms other procedures for large-scaled instances (up to 2000 variables and constraints). A extended abstract of this paper appeared in LNCS 4362, pp. 456–464, 2007.     

Schedule Recovery: Unplanned Absences in Service Operations*

The U.S. service sector loses 2.3% of all scheduled labor hours to unplanned absences, but in some industries, the total cost of unplanned absences approaches 20% of payroll expense. The principal reasons for unscheduled absences (personal illness and family issues) are unlikely to abate anytime soon. Despite this, most labor scheduling systems continue to assume perfect attendance. This oversight masks an important but rarely addressed issue in services management: how to recover from short‐notice, short‐term reductions in planned capacity. In this article, we model optimal responses to unplanned employee absences in multi‐server queueing systems that provide discrete, pay‐per‐use services for impatient customers. Our goal is to assess the performance of alternate absence recovery strategies under various staffing and scheduling regimes. We accomplish this by first developing optimal labor schedules for hypothetical service environments with unreliable workers. We then simulate unplanned employee absences, apply an absence recovery model, and compute system profits. Our absence recovery model utilizes recovery strategies such as holdover overtime, call‐ins, and temporary workers. We find that holdover overtime is an effective absence recovery strategy provided sufficient reserve capacity (maximum allowable work hours minus scheduled hours) exists. Otherwise, less precise and more costly absence recovery methods such as call‐ins and temporary help service workers may be needed. We also find that choices for initial staffing and scheduling policies, such as planned overtime and absence anticipation, significantly influence the likelihood of successful absence recovery. To predict the effectiveness of absence recovery policies under alternate staffing/scheduling strategies and operating environments, we propose an index based on initial capacity reserves.     

Estimating the Impact of Understaffing on Sales and Profitability in Retail Stores

In this study, we use hourly data on store traffic, sales, and labor from 41 stores of a large retail chain to identify the extent of understaffing in retail stores and quantify its impact on sales and profitability. Using an empirical model motivated from queueing theory, we calculate the benchmark staffing level for each store, and establish the presence of systematic understaffing during peak hours. We find that all 41 stores in our sample are systematically understaffed during a 3‐hour peak period. Eliminating understaffing in these stores can result in a significant increase in sales and profitability in these stores. Also, we examine the extent to which forecasting errors and scheduling constraints drive understaffing in retail stores and quantify their relative impacts on store profits for the retailer in our study.     

Single machine scheduling with non-availability interval and optional job rejection

This paper studies the single machine scheduling problem with availability constraints and optional job rejection. We consider the non-resumable and resumable variants, and show that the problems remain ordinary NP-hard, even with the rejection possibility extension, by presenting pseudo-polynomial dynamic-programming (DP) solutions. We also present an enhanced running time implementation of the algorithm of Kellerer and Strusevich (Algorithmica 57(4):769–795, 2010) for the resumable scenario without job rejection. This solution is adapted to efficiently solve the machine non-availability problem with a floating interval and the problem of two competing agents on a single machine, with and without optional job rejection. Numerical experiments support the efficiency of our DP implementation.