Dynamic Capacity Acquisition and Assignment under Uncertainty

Given a set of m resources and n tasks, the dynamic capacity acquisition and assignment problem seeks a minimum cost schedule of capacity acquisitions for the resources and the assignment of resources to tasks, over a given planning horizon of T periods. This problem arises, for example, in the integrated planning of locations and capacities of distribution centers (DCs), and the assignment of customers to the DCs, in supply chain applications. We consider the dynamic capacity acquisition and assignment problem in an environment where the assignment costs and the processing requirements for the tasks are uncertain. Using a scenario based approach, we develop a stochastic integer programming model for this problem. The highly non-convex nature of this model prevents the application of standard stochastic programming decomposition algorithms. We use a recently developed decomposition based branch-and-bound strategy for the problem. Encouraging preliminary computational results are provided.     

Robust optimization of internal transports at a parcel sorting center operated by Deutsche Post World Net

Competitiveness in global markets requires the ongoing identification and full utilization of improvement potential. To cut costs by means of process optimization, logistics service providers need to focus on efficient planning — not only for external but also for internal transports. This contribution will demonstrate that significant reductions in internal transports at one of the Deutsche Post World Net’s main parcel sorting centers can be achieved by applying the robust solution of a modified three-dimensional linear assignment model.     

Asymptotic Analysis of a Greedy Heuristic for the Multi-Period Single-Sourcing Problem: The Acyclic Case

The multi-period single-sourcing problem that we address in this paper can be used as a tactical tool for evaluating logistics network designs in a dynamic environment. In particular, our objective is to find an assignment of customers to facilities, as well as the location, timing and size of production and inventory levels, that minimizes total assignment, production, and inventory costs. We propose a greedy heuristic, and prove that this greedy heuristic is asymptotically optimal in a probabilistic sense for the subclass of problems where the assignment of customers to facilities is allowed to vary over time. In addition, we prove a similar result for the subclass of problems where each customer needs to be assigned to the same facility over the planning horizon, and where the demand for each customer exhibits the same seasonality pattern. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. These results suggest that the greedy heuristic may be asymptotically optimal even for the cases that we were unable to analyze theoretically.     

The generalized assignment problem with flexible jobs

The Generalized Assignment Problem (GAP) seeks an allocation of jobs to capacitated resources at minimum total assignment cost, assuming a job cannot be split among multiple resources. We consider a generalization of this broadly applicable problem in which each job must not only be assigned to a resource, but its resource consumption must also be determined within job-specific limits. In this profit-maximizing version of the GAP, a higher degree of resource consumption increases the revenue associated with a job. Our model permits a job’s revenue per unit resource consumption to decrease as a function of total resource consumption, which allows modeling quantity discounts. The objective is then to determine job assignments and resource consumption levels that maximize total profit. We develop a class of heuristic solution methods, and demonstrate the asymptotic optimality of this class of heuristics in a probabilistic sense.     

A cardinality-constrained robust model for the assignment problem in Home Care services

Home Care includes medical, paramedical and social services which are delivered to patients at their domicile rather than in hospital. Managing human and material resources in Home Care services is a difficult task, as the provider has to deal with peculiar constraints (e.g., the continuity of care, which imposes that a patient is always cared for by the same nurse) and to manage the high variability of patients’ demands. One of the main issues encountered in planning Home Care services under continuity of care requirement is the nurse-to-patient assignment. Despite the importance of this topic, the problem is only marginally addressed in the literature, where continuity of care is usually treated as a soft-constraint rather than as a hard one. Uncertainty is another relevant feature of nurse-to-patient assignment problem, and it is usually managed adopting stochastic programming or analytical policies. However, both these approaches proved to be limited, even if they improve the quality of the assignments upon those actually provided in practice. In this paper, we develop a cardinality-constrained robust assignment model, which allows exploiting the potentialities of a mathematical programming model without the necessity of generating scenarios. The developed model is tested on real-life instances related to a relevant Home Care provider operating in Italy, in order to evaluate its capability of reducing the costs related to nurses’ overtimes.     

The Army Training Mix Model

We describe a model for making decisions concerning the proper mix of TADSS (training aids, devices, simulators and simulations) and conventional training resources, and the best modes of using them to maintain soldier and unit proficiency. Given the proficiency standards, the model determines the resources needed, the training methods for using them, and the frequency with which each method needs to be repeated, in order to maintain the standards at minimum cost (sum of equipment procurement costs and operational costs). The model is illustrated with an example problem dealing with the analysis of training systems in a battalion training strategy. Our model has much wider applicability: it can be used for evaluating and determining minimum cost training strategies for other combined arms elements, higher level units and other training scenarios under a variety of circumstances.     

Linear algebra students’ modes of reasoning: Geometric representations

Main goal of our research was to document differences on the types of modes linear algebra students displayed in their responses to the questions of linear independence from two different assignments. In this paper, modes from the second assignment are discussed in detail. Second assignment was administered with the support of graphical representations through an interactive web-module. Additionally, for comparison purposes, we briefly talk about the modes from the first assignment. First assignment was administered with the support of computational devices such as calculators providing the row reduced echelon form (rref) of matrices. Sierpinska’s framework on thinking modes (2000) was considered while qualitatively documenting the aspects of 45 matrix algebra students’ modes of reasoning. Our analysis revealed 17 categories of the modes of reasoning for the second assignment, and 15 categories for the first assignment. In conclusion, the findings of our analysis support the view of the geometric representations not replacing one’s arithmetic or algebraic modes but encouraging students to utilize multiple modes in their reasoning. Specifically, geometric representations in the presence of algebraic and arithmetic modes appear to help learners begin to consider the diverse representational aspects of a concept flexibly.     

Job Release: Part of a Hierarchical System to Manage Manufacturing Lead Times in Make-to-order Companies

A methodology to manage manufacturing lead times is currently being developed by the authors. The system is specifically designed to address the needs of small- to medium-sized make-to-order companies. It involves a hierarchical production planning system in which integration between the production and marketing functions is facilitated. Considerations of capacity are included at both of the decision levels addressed—the customer enquiry stage and the job release stage. This paper describes the job release stage, showing how it is linked with the higher-level stage by controlling a hierarchy of backlog lengths. At the job release stage the released backlog length for each work centre is maintained between predetermined minimum and maximum levels. It is shown that shop floor throughput times—an important part of manufacturing lead times—can be controlled by controlling released backlog lengths. The releasing mechanism is described and it is argued that there can be many benefits of job release—including reduced shop congestion, lower work-in-progress and lower costs.     

Recent developments in Dual Resource Constrained (DRC) system research

Real world manufacturing systems are usually constrained by both machine and human resources. Human operators are often the constraining resource and transfer between workstations to process jobs when required. This kind of system is known as a Dual Resource Constrained (DRC) system and presents additional technical challenges which must be considered during planning and scheduling. These technical challenges can be categorised into the five main dimensions of job release mechanisms, job dispatching, worker flexibility, worker assignment and transfer costs. This paper aims to provide an overview of recent developments in DRC research concerned with each of these areas and also discusses some possible approaches to solving the resource scheduling problem in a DRC system. The focus is on materials published after 1995 and up to 2009. Previous reviews on DRC systems are commented on and followed by a review of recent works associated with each of the five dimensions of DRC system research. Advancements made and new methodologies proposed are discussed and future research directions are identified.     

Teaching scenario planning: Lessons from practice in academe and business

In this paper, we engage with O’Brien’s [O’Brien, F.A., 2004. Scenario planning – lessons for practice from teaching and learning. European Journal of Operational Research 152, 709–722] identification of both pitfalls in teaching scenario planning and proposed remedies for these. We consider these remedies in relation to our own experience – based on our practice in both the academic and business arenas – and we highlight further pitfalls and proposed remedies. Finally, we propose the use of “hard” multi-attribute decision analysis as a complement to “soft” scenario planning, in order to allow a more formal method of strategy evaluation against a range of constructed scenarios, This approach is intended to remedy biases that are associated with holistic evaluations – such as lexicographic ranking – where undue attention is paid to particular strategic objectives at the expense of others. From this discussion, we seek to contribute to cumulative refinement of the scenario process.     

Multi-coloring and job-scheduling with assignment and incompatibility costs

Consider a scheduling problem (P) which consists of a set of jobs to be performed within a limited number of time periods. For each job, we know its duration as an integer number of time periods, and preemptions are allowed. The goal is to assign the required number of time periods to each job while minimizing the assignment and incompatibility costs. When a job is performed within a time period, an assignment cost is encountered, which depends on the involved job and on the considered time period. In addition, for some pairs of jobs, incompatibility costs are encountered if they are performed within common time periods. (P) can be seen as an extension of the multi-coloring problem. We propose various solution methods for (P) (namely a greedy algorithm, a descent method, a tabu search and a genetic local search), as well as an exact approach. All these methods are compared on different types of instances.     

Greedy approaches for a class of nonlinear Generalized Assignment Problems

The traditional Generalized Assignment Problem (GAP) seeks an assignment of customers to facilities that minimizes the sum of the assignment costs while respecting the capacity of each facility. We consider a nonlinear GAP where, in addition to the assignment costs, there is a nonlinear cost function associated with each facility whose argument is a linear function of the customers assigned to the facility. We propose a class of greedy algorithms for this problem that extends a family of greedy algorithms for the GAP. The effectiveness of these algorithms is based on our analysis of the continuous relaxation of our problem. We show that there exists an optimal solution to the continuous relaxation with a small number of fractional variables and provide a set of dual multipliers associated with this solution. This set of dual multipliers is then used in the greedy algorithm. We provide conditions under which our greedy algorithm is asymptotically optimal and feasible under a stochastic model of the parameters.     

Characterization of facility assignment costs for a location-inventory model under truckload distribution

We consider a two-stage distribution system, where the first stage consists of potential distribution centres (DCs) and the second stage consists of geographically dispersed existing retailers. Our goal is to determine the set of open DCs and assignment of open DCs to retailers simultaneously with inventory decisions of retailers. In addition to the DC-specific fixed facility location costs, we explicitly model the inventory replenishment and holding costs at the retailers and truckload transportation costs between the DCs and the retailers. The transportation costs are subject to truck/cargo capacity, leading to an integrated location-inventory problem with explicit cargo costs. We develop a mixed-integer nonlinear model and analyse its structural properties leading to exact expressions for the so-called implied facility assignment costs and imputed per-unit per-mile transportation costs. These expressions analytically demonstrate the interplay between strategic location and tactical inventory/transportation decisions in terms of resulting operational costs. Although both the theory and practice of integrated logistics have recognized the fact that strategic and tactical decisions are interrelated, to the best of our knowledge, our paper is the first to offer closed-form results demonstrating the relationship explicitly. We propose an efficient solution approach utilizing the implied facility assignment costs and we demonstrate that significant savings are realizable when the inventory decisions and cargo costs are modelled explicitly for facility location purposes.     

A production scheduling heuristic for an electronics manufacturer with sequence-dependent setup costs

In this paper, we develop a three-step heuristic to address a production scheduling problem at a high volume assemble-to-order electronics manufacturer. The heuristic provides a solution for scheduling multiple product families on parallel, identical production lines so as to minimize setup costs. The heuristic involves assignment, sequencing, and time scheduling steps, with an optimization approach developed for each step. For the most complex step, the sequencing step, we develop a greedy randomized adaptive search procedure (GRASP). We compare the setup costs resulting from the use of our scheduling heuristic against a heuristic previously developed and implemented at the electronics manufacturer that assumes approximately equal, sequence-independent, setup costs. By explicitly considering the sequence-dependent setup costs and applying GRASP, our empirical results show a reduction in setups costs for an entire factory of 14–21% with a range of single production line reductions from 0% to 49%.     

Strong stability of Nash equilibria in load balancing games

We study strong stability of Nash equilibria in load balancing games of m(m 2)identical servers,in which every job chooses one of the m servers and each job wishes to minimize its cost,given by the workload of the server it chooses.A Nash equilibrium(NE)is a strategy profile that is resilient to unilateral deviations.Finding an NE in such a game is simple.However,an NE assignment is not stable against coordinated deviations of several jobs,while a strong Nash equilibrium(SNE)is.We study how well an NE approximates an SNE.Given any job assignment in a load balancing game,the improvement ratio(IR)of a deviation of a job is defined as the ratio between the pre-and post-deviation costs.An NE is said to be aρ-approximate SNE(ρ1)if there is no coalition of jobs such that each job of the coalition will have an IR more thanρfrom coordinated deviations of the coalition.While it is already known that NEs are the same as SNEs in the 2-server load balancing game,we prove that,in the m-server load balancing game for any given m 3,any NE is a(5/4)-approximate SNE,which together with the lower bound already established in the literature yields a tight approximation bound.This closes the final gap in the literature on the study of approximation of general NEs to SNEs in load balancing games.To establish our upper bound,we make a novel use of a graph-theoretic tool.     

“货到人”拣选系统机器人任务分配的鲁棒双层规划模型

在电商“货到人”拣选系统中,如何调度系统中的机器人并对任务进行合理地分配决定着整个系统的运行效率与成本。分析“货到人”拣选系统作业流程,建立机器人数量配置、机器人调度与机器人任务分配的双层规划模型。上层模型以批量订单完成总成本最小为目标函数,以机器人调度为决策变量,构建整数规划模型;下层模型以机器人完成所有任务的平均空闲率最小为目标函数,以任务分配为决策变量,考虑机器人在完成任务过程中由于调度、避障、路径规划等导致的行走距离不确定因素,构建鲁棒优化模型。上层的调度结果制约了下层的最小平均空闲率,下层的任务分配结果影响上层的最小成本,上下层结果共同决定机器人配置决策。利用遗传算法求解模型,通过实例仿真验证了模型的有效性。     

Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures

Suppose that there are n jobs and n machines and it costs c_ij to execute job i on machine j. The assignment problem concerns the determination of a one‐to‐one assignment of jobs onto machines so as to minimize the cost of executing all the jobs. When the c_ij are independent and identically distributed exponentials of mean 1, Parisi [Technical Report cond‐mat/9801176, xxx LANL Archive, 1998] made the beautiful conjecture that the expected cost of the minimum assignment equals . Coppersmith and Sorkin [Random Structures Algorithms 15 ( 6 ), 113–144] generalized Parisi's conjecture to the average value of the smallest k‐assignment when there are n jobs and m machines. Building on the previous work of Sharma and Prabhakar [Proc 40th Annu Allerton Conf Communication Control and Computing, 20 , 657–666] and Nair [Proc 40th Annu Allerton Conf Communication Control and Computing, 17 , 667–673], we resolve the Parisi and Coppersmith‐Sorkin conjectures. In the process we obtain a number of combinatorial results which may be of general interest.© 2005 Wiley Periodicals, Inc. Random Struct. Alg. 2005     

Optimising a general repair kit problem with a service constraint

Field services are a particular type of after-sales service performed at the customer’s location where technicians repair malfunctioning machines. The inventory decisions about which spare part types to take to the repair site and in what quantities is called the repair kit problem. This problem is characterized by an order-based performance measure since a customer is only satisfied when all required spare parts are available to fix the machine. As a result, the service level in the decision making process is defined as a job fill rate. In this paper we derive a closed-form expression for the expected service level and total costs for the repair kit problem in a general setting, where multiple units of each part type can be used in a multi-period problem. Such an all-or-nothing strategy is a new characteristic to investigate, but commonly used in practice. Namely, items are only taken from the inventory when all items to perform the repair are available in the right quantity. We develop a new algorithm to determine the contents of the repair kit both for a service and cost model while incorporating this new expression for the job fill rate. We show that the algorithm finds solutions which differ on average 0.2% from optimal costs. We perform a case study to test the performance of the algorithm in practice. Our approach results in service level improvements of more than 30% against similar holding costs.     

Freight transportation in railway networks with automated terminals: A mathematical model and MIP heuristic approaches

In this paper we propose a planning procedure for serving freight transportation requests in a railway network with fast transfer equipment at terminals. We consider a transportation system where different customers make their requests (orders) for moving boxes, i.e., either containers or swap bodies, between different origins and destinations, with specific requirements on delivery times. The decisions to be taken concern the route (and the corresponding sequence of trains) that each box follows in the network and the assignment of boxes to train wagons, taking into account that boxes can change more than one train and that train timetables are fixed.The planning procedure includes a pre-analysis step to determine all the possible sequences of trains for serving each order, followed by the solution of a 0-1 linear programming problem to find the optimal assignment of each box to a train sequence and to a specific wagon for each train in the sequence. This latter is a generalized assignment problem which is NP-hard. Hence, in order to find good solutions in acceptable computation times, two MIP heuristic approaches are proposed and tested through an experimental analysis considering realistic problem instances.     

Optimal policy for a dynamic,non-stationary,stochastic inventory problem with capacity commitment

This paper studies a single-product, dynamic, non-stationary, stochastic inventory problem with capacity commitment, in which a buyer purchases a fixed capacity from a supplier at the beginning of a planning horizon and the buyer’s total cumulative order quantity over the planning horizon is constrained with the capacity. The objective of the buyer is to choose the capacity at the beginning of the planning horizon and the order quantity in each period to minimize the expected total cost over the planning horizon. We characterize the structure of the minimum sum of the expected ordering, storage and shortage costs in a period and thereafter and the optimal ordering policy for a given capacity. Based on the structure, we identify conditions under which a myopic ordering policy is optimal and derive an equation for the optimal capacity commitment. We then use the optimal capacity and the myopic ordering policy to evaluate the effect of the various parameters on the minimum expected total cost over the planning horizon.