Capacity allocation for demand of different customer-product-combinations with cancellations, no-shows, and overbooking when there is a sequential delivery of service

We consider a problem where different classes of customers can book different types of services in advance and the service company has to respond immediately to the booking request confirming or rejecting it. Due to the possibility of cancellations before the day of service, or no-shows at the day of service, overbooking the given capacity is a viable decision. The objective of the service company is to maximize profit made of class-type specific revenues, refunds for cancellations or no-shows as well as the cost of overtime. For the calculation of the latter, information of the underlying appointment schedule is required. Throughout the paper we will relate the problem to capacity allocation in radiology services. Drawing upon ideas from revenue management, overbooking, and appointment scheduling we model the problem as a Markov decision process in discrete time which due to proper aggregation can be optimally solved with an iterative stochastic dynamic programming approach. In an experimental study we successfully apply the approach to a real world problem with data from the radiology department of a hospital. Furthermore, we compare the optimal policy to four heuristic policies, of whom one is currently in use. We can show that the optimal policy significantly improves the currently used policy and that a nested booking limit type policy closely approximates the optimal policy and is thus recommended for use in practice.     

Algorithms for a stochastic selective travelling salesperson problem

In this paper, the selective travelling salesperson problem with stochastic service times, travel times, and travel costs (SSTSP) is addressed. In the SSTSP, service times, travel times and travel costs are known a priori only probabilistically. A non-negative value of reward for providing service is associated with each customer and there is a pre-specified limit on the duration of the solution tour. It is assumed that not all potential customers can be visited within this tour duration limit, even under the best circumstances. And, thus, a subset of customers must be selected. The objective of the SSTSP is to design an a priori tour that visits each chosen customer once such that the total profit (total reward collected by servicing customers minus travel costs) is maximized and the probability that the total actual tour duration exceeds a given threshold is no larger than a chosen probability value. We formulate the SSTSP as a chance-constrained stochastic program and propose both exact and heuristic approaches for solving it. Computational experiments indicate that the exact algorithm is able to solve small- and moderate-size problems to optimality and the heuristic can provide near-optimal solutions in significantly reduced computing time.     

带次模惩罚和随机需求的设施选址问题

考虑带次模惩罚和随机需求的设施选址问题,目的是开设设施集合的一个子集,把客户连接到开设的设施上并对没有连接的客户进行惩罚,使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小. 根据该问题的特殊结构,给出原始对偶3-近似算法. 在算法的第一步,构造了一组对偶可行解;在第二步中构造了对应的一组原始整数可行解,这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合. 最后,证明了算法在多项式时间内可以完成,并且算法所给的整数解不会超过最优解的3倍.     

The mixed capacitated general routing problem under uncertainty

We study the General Routing Problem defined on a mixed graph and with stochastic demands. The problem under investigation is aimed at finding the minimum cost set of routes to satisfy a set of clients whose demand is not deterministically known. Since each vehicle has a limited capacity, the demand uncertainty occurring at some clients affects the satisfaction of the capacity constraints, that, hence, become stochastic. The contribution of this paper is twofold: firstly we present a chance-constrained integer programming formulation of the problem for which a deterministic equivalent is derived. The introduction of uncertainty into the problem poses severe computational challenges addressed by the design of a branch-and-cut algorithm, for the exact solution of limited size instances, and of a heuristic solution approach exploring promising parts of the search space. The effectiveness of the solution approaches is shown on a probabilistically constrained version of the benchmark instances proposed in the literature for the mixed capacitated general routing problem.     

An Asset Liability Management Model for Casualty Insurers: Complexity Reduction vs. Parameterized Decision Rules

In this paper we study possibilities for complexity reductions in large scale stochastic programming problems with specific reference to the asset liability management (ALM) problem for casualty insurers. We describe a dynamic, stochastic portfolio selection model, within which the casualty insurer maximizes a concave objective function, indicating that the company perceives itself as risk averse. In this context we examine the sensitivity of the solution to the quality and accuracy with which economic uncertainties are represented in the model. We demonstrate a solution method that combines two solution approaches: A truly stochastic, dynamic solution method that requires scenario aggregation, and a solution method based on ex ante decision rules, that allow for a greater number of scenarios. This dynamic/fix mix decision policy, which facilitates a huge number of outcomes, is then compared to a fully dynamic decision policy, requiring fewer outcomes. We present results from solving the model. Basically we find that the insurance company is likely to prefer accurate representation of uncertainties. In order to accomplish this, it will accept to calculate its current portfolio using parameterized decision rules.     

带有异常点的平方度量设施选址问题

传统的设施选址问题一般假设所有顾客都被服务,考虑到异常点的存在不仅会增加总费用（设施的开设费用与连接费用之和）,也会影响到对其他顾客的服务质量。研究异常点在最终方案中允许不被服务的情况,称之为带有异常点的平方度量设施选址问题。该问题是无容量设施选址问题的推广。问题可描述如下：给定设施集合、顾客集,以及设施开设费用和顾客连接费用,目标是选择设施的子集开设以满足顾客的需求,使得设施开设费用与连接费用之和最小。利用原始对偶技巧设计了近似算法,证明了该算法的近似比是9。     

Joint-replenishment problem under stochastic demands with backorders-lost sales mixtures,controllable lead times,and investment to reduce the major ordering cost

In this paper, we study the periodic-review stochastic Joint-replenishment Problem (JRP), with backorders-lost sales mixtures, controllable lead times, and investment to reduce the major ordering cost. The purpose is to determine a strict cyclic replenishment policy, the length of lead times, and the major ordering cost that minimize the total system cost. We first present an effective heuristic algorithm to approach the problem. However, results illustrate how computationally expensive the algorithm would be for a practical application. Hence, we then propose an efficient and more practically applicable solution procedure. In particular, approximating part of the cost function with its second-order Taylor series expansion, we obtain an expression that resembles the deterministic cost structure. Therefore, the problem can be approached exploiting a standard algorithm suitable for the deterministic JRP. Numerical tests compare the performances of the algorithms developed and show that the approximated approach is actually promising for a practical application.     

Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

A discrete bilevel brain storm algorithm for solving a sales territory design problem: a case study

A sales territory design problem faced by a manufacturing company that supplies products to a group of customers located in a service region is addressed in this paper. The planning process of designing the territories has the objective to minimizing the total dispersion of the customers without exceeding a limited budget assigned to each territory. Once territories have been determined, a salesperson has to define the day-by-day routes to satisfy the demand of customers. Currently, the company has established a service level policy that aims to minimize total waiting times during the distribution process. Also, each territory is served by a single salesperson. A novel discrete bilevel optimization model for the sales territory design problem is proposed. This problem can be seen as a bilevel problem with a single leader and multiple independent followers, in which the leader’s problem corresponds to the design of territories (manager of the company), and the routing decision for each territory corresponds to each follower. The hierarchical nature of the current company’s decision-making process triggers some particular characteristics of the bilevel model. A brain storm algorithm that exploits these characteristics is proposed to solve the discrete bilevel problem. The main features of the proposed algorithm are that the workload is used to verify the feasibility and to cluster the leader’s solutions. In addition, four discrete mechanisms are used to generate new solutions, and an elite set of solutions is considered to reduce computational cost. This algorithm is used to solve a real case study, and the results are compared against the current solution given by the company. Results show a reduction of more than 20% in the current costs with the solution obtained by the proposed algorithm. Furthermore, a sensitivity analysis is performed, providing interesting managerial insights to improve the current operations of the company.     

Minimizing weighted mean absolute deviation of job completion times from their weighted mean

We address a single-machine scheduling problem where the objective is to minimize the weighted mean absolute deviation of job completion times from their weighted mean. This problem and its precursors aim to achieve the maximum admissible level of service equity. It has been shown earlier that the unweighted version of this problem is NP-hard in the ordinary sense. For that version, a pseudo-polynomial time dynamic program and a 2-approximate algorithm are available. However, not much (except for an important solution property) exists for the weighted version. In this paper, we establish the relationship between the optimal solution to the weighted problem and a related one in which the deviations are measured from the weighted median (rather than the mean) of the job completion times; this generalizes the 2-approximation result mentioned above. We proceed to give a pseudo-polynomial time dynamic program, establishing the ordinary NP-hardness of the problem in general. We then present a fully-polynomial time approximation scheme as well. Finally, we report the findings from a limited computational study on the heuristic solution of the general problem. Our results specialize easily to the unweighted case; they also lead to an approximation of the set of schedules that are efficient with respect to both the weighted mean absolute deviation and the weighted mean completion time.     

Multi-source facility location–allocation and inventory problem

We consider a joint facility location–allocation and inventory problem that incorporates multiple sources of warehouses. The problem is motivated by a real situation faced by a multinational applied chemistry company. In this problem, multiple products are produced in several plants. Warehouse can be replenished by several plants together because of capabilities and capacities of plants. Each customer in this problem has stochastic demand and certain amount of safety stock must be maintained in warehouses so as to achieve certain customer service level. The problem is to determine number and locations of warehouses, allocation of customers demand and inventory levels of warehouses. The objective is to minimize the expected total cost with the satisfaction of desired demand weighted average customer lead time and desired cycle service level. The problem is formulated as a mixed integer nonlinear programming model. Utilizing approximation and transformation techniques, we develop an iterative heuristic method for the problem. An experiment study shows that the proposed procedure performs well in comparison with a lower bound.     

Joint-optimization of inventory policies on a multi-product multi-echelon pharmaceutical system with batching and ordering constraints

This paper presents a methodology to find near-optimal joint inventory control policies for the real case of a one-warehouse, n-retailer distribution system of infusion solutions at a University Medical Center in France. We consider stochastic demand, batching and order-up-to level policies as well as aspects particular to the healthcare setting such as emergency deliveries, required service level rates and a new constraint on the ordering policy that fits best the hospital’s interests instead of abstract ordering costs. The system is modeled as a Markov chain with an objective to minimize the stock-on-hand value for the overall system. We provide the analytical structure of the model to show that the optimal reorder point of the policy at both echelons is easily derived from a simple probability calculation. We also show that the optimal policy at the care units is to set the order-up-to level one unit higher than the reorder point. We further demonstrate that optimizing the care units in isolation is optimal for the joint multi-echelon, n-retailer problem. A heuristic algorithm is presented to find the near-optimal order-up-to level of the policy of each product at the central pharmacy; all other policy parameters are guaranteed optimal via the structure provided by the model. Comparison of our methodology versus that currently in place at the hospital showed a reduction of approximately 45% in the stock-on-hand value while still respecting the service level requirements.     

Stochastic cyclic scheduling problem in synchronous assembly and production lines

In this paper we address the stochastic cyclic scheduling problem in synchronous assembly and production lines. Synchronous lines are widely used in the production and assembly of various goods such as automobiles or household appliances. We consider cycle time minimisation (or throughput rate maximisation) as the objective of the scheduling problem with the assumption that the processing times are independent random variables. We first discuss the two-station case and present a lower bounding scheme and an approximate solution procedure for the scheduling problem. For the general case of the problem, two heuristic solution procedures are presented. An extension of the two-station lower bound to the general case of the problem is also discussed. The performance of the proposed heuristics on randomly generated problems is documented, and the impact of scheduling decisions on problems with different levels of variability in processing times are analysed. We also analyse the problem of sequence determination when the available information is limited to the expected values of individual processing times.     

Capacity allocation problem with random demands for the rail container carrier

In this paper, we consider the formulation and heuristic algorithm for the capacity allocation problem with random demands in the rail container transportation. The problem is formulated as the stochastic integer programming model taking into account matches in supply and demand of rail container transportation. A heuristic algorithm for the stochastic integer programming model is proposed. The solution to the model is found by maximizing the expected total profit over the possible control decisions under the uncertainty of demands. Finally, we give numerical experiments to demonstrate the efficiency of the heuristic algorithm.     

Minimizing earliness and tardiness costs in stochastic scheduling

We address the single-machine stochastic scheduling problem with an objective of minimizing total expected earliness and tardiness costs, assuming that processing times follow normal distributions and due dates are decisions. We develop a branch and bound algorithm to find optimal solutions to this problem and report the results of computational experiments. We also test some heuristic procedures and find that surprisingly good performance can be achieved by a list schedule followed by an adjacent pairwise interchange procedure.     

Rollout Algorithms for Combinatorial Optimization

We consider the approximate solution of discrete optimization problems using procedures that are capable of magnifying the effectiveness of any given heuristic algorithm through sequential application. In particular, we embed the problem within a dynamic programming framework, and we introduce several types of rollout algorithms, which are related to notions of policy iteration. We provide conditions guaranteeing that the rollout algorithm improves the performance of the original heuristic algorithm. The method is illustrated in the context of a machine maintenance and repair problem.     

A heuristic procedure for stochastic integer programs with complete recourse

In this paper, we propose a successive approximation heuristic which solves large stochastic mixed-integer programming problem with complete fixed recourse. We refer to this method as the Scenario Updating Method, since it solves the problem by considering only a subset of scenarios which is updated at each iteration. Only those scenarios which imply a significant change in the objective function are added. The algorithm is terminated when no such scenarios are available to enter in the current scenario subtree. Several rules to select scenarios are discussed. Bounds on heuristic solutions are computed by relaxing some of the non-anticipativity constraints. The proposed procedure is tested on a multistage stochastic batch-sizing problem.     

The orienteering problem with stochastic travel and service times

In this paper, we introduce a variant of the orienteering problem in which travel and service times are stochastic. If a delivery commitment is made to a customer and is completed by the end of the day, a reward is received, but if a commitment is made and not completed, a penalty is incurred. This problem reflects the challenges of a company who, on a given day, may have more customers than it can serve. In this paper, we discuss special cases of the problem that we can solve exactly and heuristics for general problem instances. We present computational results for a variety of parameter settings and discuss characteristics of the solution structure.     

A random-key genetic algorithm for the generalized traveling salesman problem

The generalized traveling salesman problem is a variation of the well-known traveling salesman problem in which the set of nodes is divided into clusters; the objective is to find a minimum-cost tour passing through one node from each cluster. We present an effective heuristic for this problem. The method combines a genetic algorithm (GA) with a local tour improvement heuristic. Solutions are encoded using random keys, which circumvent the feasibility problems encountered when using traditional GA encodings. On a set of 41 standard test problems with symmetric distances and up to 442 nodes, the heuristic found solutions that were optimal in most cases and were within 1% of optimality in all but the largest problems, with computation times generally within 10 seconds. The heuristic is competitive with other heuristics published to date in both solution quality and computation time.     

Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines

We study the stochastic online scheduling on m uniform machines with the objective to minimize the expected value of total weighted completion times of a set of jobs that arrive over time. For each job, the processing time is a random variable, and the distribution of processing time is unknown in advance. The actual processing time could be known only when the job is completed. For the problem, we propose a policy which is proved to be asymptotically optimal when the processing times and weights are uniformly bounded, i.e. the relative error of the solution achieved by our policy approaches zero as the number of jobs increases to infinity.