Organizational, systems and human issues in production planning, scheduling and control

With global markets and global competition, pressures are placed on manufacturing organizations to compress order fulfillment times, meet delivery commitments consistently and also maintain efficiency in operations to address cost issues. This chapter argues for a process perspective on planning, scheduling and control that integrates organizational planning structures, information systems as well as human decision makers. The chapter begins with a reconsideration of the gap between theory and practice, in particular for classical scheduling theory and hierarchical production planning and control. A number of the key studies of industrial practice are then described and their implications noted. A recent model of scheduling practice derived from a detailed study of real businesses is described. Socio-technical concepts are then introduced and their implications for the design and management of planning, scheduling and control systems are discussed. The implications of adopting a process perspective are noted along with insights from knowledge management. An overview is presented of a methodology for the (re-)design of planning, scheduling and control systems that integrates organizational, system and human perspectives. The most important messages from the chapter are then summarized.

Optimization models and methods for real-time transportation planning in forestry

Lors du transport du bois de la for��t vers les usines, de nombreux ��v��nements impr��vus peuvent se produire, ��v��nements qui perturbent les trajets pr��vus (par exemple, en raison des conditions m��t��o, des feux de for��t, de la pr��sence de nouveaux chargements, etc.). Lorsque de tels ��v��nements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit ��tre d��tourn�� vers un chemin alternatif. En l���absence d���informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-m��me "ferm��" suite �� un ��v��nement impr��vu. Il est donc essentiel de fournir aux chauffeurs des informations en temps r��el, en particulier des suggestions de chemins alternatifs lorsqu���une route pr��vue s���av��re impraticable. Les possibilit��s de recours en cas d���impr��vus d��pendent des caract��ristiques de la cha��ne logistique ��tudi��e comme la pr��sence de camions auto-chargeurs et la politique de gestion du transport. Nous pr��sentons trois articles traitant de contextes d���application diff��rents ainsi que des mod��les et des m��thodes de r��solution adapt��s �� chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l���ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent ��tre faits pour minimiser les changements apport��s au plan initial. Bien que la flotte de camions soit homog��ne, il y a un ordre de priorit�� des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est ��galement une priorit��. ��tant donn�� que les cons��quences des ��v��nements impr��vus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l���approche propos��e traite d���abord l���annulation et le retard d���un seul voyage, puis elle est g��n��ralis��e pour traiter des ��v��nements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impact��s durant la m��me semaine de telle sorte qu���une chargeuse soit libre au moment de l���arriv��e du camion �� la fois au site forestier et �� l���usine. De cette fa��on, les voyages des autres camions ne seront pas mo- difi��s. Cette approche fournit aux r��partiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient ��tre obtenues si le r��partiteur ��tait autoris�� �� apporter plus de modifications au plan initial. Dans le second article, nous consid��rons un contexte o�� un seul voyage �� la fois est communiqu�� aux chauffeurs. Le r��partiteur attend jusqu����� ce que le chauffeur termine son voyage avant de lui r��v��ler le prochain voyage. Ce contexte est plus souple et offre plus de possibilit��s de recours en cas d���impr��vus. En plus, le probl��me hebdomadaire peut ��tre divis�� en des probl��mes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des p��riodes limit��es durant la journ��e. Nous utilisons un mod��le de programmation math��matique bas�� sur un r��seau espace-temps pour r��agir aux perturbations. Bien que ces derni��res puissent avoir des effets diff��rents sur le plan de transport initial, une caract��ristique cl�� du mod��le propos�� est qu���il reste valable pour traiter tous les impr��vus, quelle que soit leur nature. En effet, l���impact de ces ��v��nements est captur�� dans le r��seau espace-temps et dans les param��tres d���entr��e plut��t que dans le mod��le lui-m��me. Le mod��le est r��solu pour la journ��e en cours chaque fois qu���un ��v��nement impr��vu est r��v��l��. Dans le dernier article, la flotte de camions est h��t��rog��ne, comprenant des camions avec des chargeuses �� bord. La configuration des routes de ces camions est diff��rente de celle des camions r��guliers, car ils ne doivent pas ��tre synchronis��s avec les chargeuses. Nous utilisons un mod��le math��matique o�� les colonnes peuvent ��tre facilement et naturellement interpr��t��es comme des itin��raires de camions. Nous r��solvons ce mod��le en utilisant la g��n��ration de colonnes. Dans un premier temps, nous relaxons l���int��gralit�� des variables de d��cision et nous consid��rons seulement un sous-ensemble des itin��raires r��alisables. Les itin��raires avec un potentiel d���am��lioration de la solution courante sont ajout��s au mod��le de mani��re it��rative. Un r��seau espace-temps est utilis�� �� la fois pour repr��senter les impacts des ��v��nements impr��vus et pour g��n��rer ces itin��raires. La solution obtenue est g��n��ralement fractionnaire et un algorithme de branch-and-price est utilis�� pour trouver des solutions enti��res. Plusieurs sc��narios de perturbation ont ��t�� d��velopp��s pour tester l���approche propos��e sur des ��tudes de cas provenant de l���industrie foresti��re canadienne et les r��sultats num��riques sont pr��sent��s pour les trois contextes.

Tabu search for the cyclic bandwidth problem

International audience

Iterated responsive threshold search for the quadratic multiple knapsack problem

International audience

Vehicle Routing Problems that Minimize the Completion Time: Heuristics, Worst-Case Analyses, and Computational Results

In the standard Vehicle Routing Problem (VRP), we route a fleet of vehicles to deliver the demands of all customers such that the total distance traveled by the fleet is minimized. In this dissertation, we study variants of the VRP that minimize the completion time, i.e., we minimize the distance of the longest route. We call it the min-max objective function. In applications such as disaster relief efforts and military operations, the objective is often to finish the delivery or the task as soon as possible, not to plan routes with the minimum total distance. Even in commercial package delivery nowadays, companies are investing in new technologies to speed up delivery instead of focusing merely on the min-sum objective. In this dissertation, we compare the min-max and the standard (min-sum) objective functions in a worst-case analysis to show that the optimal solution with respect to one objective function can be very poor with respect to the other. The results motivate the design of algorithms specifically for the min-max objective. We study variants of min-max VRPs including one problem from the literature (the min-max Multi-Depot VRP) and two new problems (the min-max Split Delivery Multi-Depot VRP with Minimum Service Requirement and the min-max Close-Enough VRP). We develop heuristics to solve these three problems. We compare the results produced by our heuristics to the best-known solutions in the literature and find that our algorithms are effective. In the case where benchmark instances are not available, we generate instances whose near-optimal solutions can be estimated based on geometry. We formulate the Vehicle Routing Problem with Drones and carry out a theoretical analysis to show the maximum benefit from using drones in addition to trucks to reduce delivery time. The speed-up ratio depends on the number of drones loaded onto one truck and the speed of the drone relative to the speed of the truck.

Multi-level, Multi-stage and Stochastic Optimization Models for Energy Conservation in Buildings for Federal, State and Local Agencies

Energy Conservation Measure (ECM) project selection is made difficult given real-world constraints, limited resources to implement savings retrofits, various suppliers in the market and project financing alternatives. Many of these energy efficient retrofit projects should be viewed as a series of investments with annual returns for these traditionally risk-averse agencies. Given a list of ECMs available, federal, state and local agencies must determine how to implement projects at lowest costs. The most common methods of implementation planning are suboptimal relative to cost. Federal, state and local agencies can obtain greater returns on their energy conservation investment over traditional methods, regardless of the implementing organization. This dissertation outlines several approaches to improve the traditional energy conservations models. Any public buildings in regions with similar energy conservation goals in the United States or internationally can also benefit greatly from this research. Additionally, many private owners of buildings are under mandates to conserve energy e.g., Local Law 85 of the New York City Energy Conservation Code requires any building, public or private, to meet the most current energy code for any alteration or renovation. Thus, both public and private stakeholders can benefit from this research. The research in this dissertation advances and presents models that decision-makers can use to optimize the selection of ECM projects with respect to the total cost of implementation. A practical application of a two-level mathematical program with equilibrium constraints (MPEC) improves the current best practice for agencies concerned with making the most cost-effective selection leveraging energy services companies or utilities. The two-level model maximizes savings to the agency and profit to the energy services companies (Chapter 2). An additional model presented leverages a single congressional appropriation to implement ECM projects (Chapter 3). Returns from implemented ECM projects are used to fund additional ECM projects. In these cases, fluctuations in energy costs and uncertainty in the estimated savings severely influence ECM project selection and the amount of the appropriation requested. A risk aversion method proposed imposes a minimum on the number of ���of projects completed in each stage. A comparative method using Conditional Value at Risk is analyzed. Time consistency was addressed in this chapter. This work demonstrates how a risk-based, stochastic, multi-stage model with binary decision variables at each stage provides a much more accurate estimate for planning than the agency���s traditional approach and deterministic models. Finally, in Chapter 4, a rolling-horizon model allows for subadditivity and superadditivity of the energy savings to simulate interactive effects between ECM projects. The approach makes use of inequalities (McCormick, 1976) to re-express constraints that involve the product of binary variables with an exact linearization (related to the convex hull of those constraints). This model additionally shows the benefits of learning between stages while remaining consistent with the single congressional appropriations framework.

Essays on Supply Chain Finance

I study how a larger party within a supply chain could use its superior knowledge about its partner, who is considered to be financially constrained, to help its partner gain access to cheap finance. In particular, I consider two scenarios: (i) Retailer intermediation in supplier finance and (ii) The Effectiveness of Supplier Buy Back Finance. In the fist chapter, I study how a large buyer could help small suppliers obtain financing for their operations. Especially in developing economies, traditional financing methods can be very costly or unavailable to such suppliers. In order to reduce channel costs, in recent years large buyers started to implement their own financing methods that intermediate between suppliers and financing institutions. In this paper, I analyze the role and efficiency of buyer intermediation in supplier financing. Building a game-theoretical model, I show that buyer intermediated financing can significantly improve supply chain performance. Using data from a large Chinese online retailer and through structural regression estimation based on the theoretical analysis, I demonstrate that buyer intermediation induces lower interest rates and wholesale prices, increases order quantities, and boosts supplier borrowing. The analysis also shows that the retailer systematically overestimates the consumer demand. Based on counterfactual analysis, I predict that the implementation of buyer intermediated financing for the online retailer in 2013 improved channel profits by 18.3%, yielding more than $68M projected savings. In the second chapter, I study a novel buy-back financing scheme employed by large manufacturers in some emerging markets. A large manufacturer can secure financing for its budget-constrained downstream partners by assuming a part of the risk for their inventory by committing to buy back some unsold units. Buy back commitment could help a small downstream party secure a bank loan and further induce a higher order quantity through better allocation of risk in the supply chain. However, such a commitment may undermine the supply chain performance as it imposes extra costs on the supplier incurred by the return of large or costly-to-handle items. I first theoretically analyze the buy-back financing contract employed by a leading Chinese automative manufacturer and some variants of this contracting scheme. In order to measure the effectiveness of buy-back financing contracts, I utilize contract and sales data from the company and structurally estimate the theoretical model. Through counterfactual analysis, I study the efficiency of various buy-back financing schemes and compare them to traditional financing methods. I find that buy-back contract agreements can improve channel efficiency significantly compared to simple contracts with no buy-back, whether the downstream retailer can secure financing on its own or not.

Mathematical Programming Models for Influence Maximization on Social Networks

In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.

Artificial immune systems

The human immune system has numerous properties that make it ripe for exploitation in the computational domain, such as robustness and fault tolerance, and many different algorithms, collectively termed Artificial Immune Systems (AIS), have been inspired by it. Two generations of AIS are currently in use, with the first generation relying on simplified immune models and the second generation utilising interdisciplinary collaboration to develop a deeper understanding of the immune system and hence produce more complex models. Both generations of algorithms have been successfully applied to a variety of problems, including anomaly detection, pattern recognition, optimisation and robotics. In this chapter an overview of AIS is presented, its evolution is discussed, and it is shown that the diversification of the field is linked to the diversity of the immune system itself, leading to a number of algorithms as opposed to one archetypal system. Two case studies are also presented to help provide insight into the mechanisms of AIS; these are the idiotypic network approach and the Dendritic Cell Algorithm.

MULTI-UNIT ACCIDENT CONTRIBUTIONS TO U.S. NUCLEAR REGULATORY COMMISSION QUANTITATIVE HEALTH OBJECTIVES: A SAFETY GOAL POLICY ANALYSIS USING MODELS FROM STATE-OF-THE-ART REACTOR CONSEQUENCE ANALYSES

The U.S. Nuclear Regulatory Commission implemented a safety goal policy in response to the 1979 Three Mile Island accident. This policy addresses the question ���How safe is safe enough?��� by specifying quantitative health objectives (QHOs) for comparison with results from nuclear power plant (NPP) probabilistic risk analyses (PRAs) to determine whether proposed regulatory actions are justified based on potential safety benefit. Lessons learned from recent operating experience���including the 2011 Fukushima accident���indicate that accidents involving multiple units at a shared site can occur with non-negligible frequency. Yet risk contributions from such scenarios are excluded by policy from safety goal evaluations���even for the nearly 60% of U.S. NPP sites that include multiple units. This research develops and applies methods for estimating risk metrics for comparison with safety goal QHOs using models from state-of-the-art consequence analyses to evaluate the effect of including multi-unit accident risk contributions in safety goal evaluations.

Design of evacuation plans for densely urbanised city centres

The high population density and tightly packed nature of some city centres make emergency planning for these urban spaces especially important, given the potential for human loss in case of disaster. Historic and recent events have made emergency service planners particularly conscious of the need for preparing evacuation plans in advance. This paper discusses a methodological approach for assisting decision-makers in designing urban evacuation plans. The approach aims at quickly and safely moving the population away from the danger zone into shelters. The plans include determining the number and location of rescue facilities, as well as the paths that people should take from their building to their assigned shelter in case of an occurrence requiring evacuation. The approach is thus of the location���allocation���routing type, through the existing streets network, and takes into account the trade-offs among different aspects of evacuation actions that inevitably come up during the planning stage. All the steps of the procedure are discussed and systematised, along with computational and practical implementation issues, in the context of a case study ��� the design of evacuation plans for the historical centre of an old European city.

M��thode de recherche �� grand voisinage pour un probl��me de tourn��es de v��hicules avec flotte priv��e et transporteur externe

Dans ce m��moire, nous ��tudions un probl��me de tourn��es de v��hicules dans lequel une flotte priv��e de v��hicules n���a pas la capacit�� suffisante pour desservir les demandes des clients. Dans un tel cas, on fait appel �� un transporteur externe. Ce dernier n���a aucune contrainte de capacit��, mais un co��t est encouru lorsqu���un client lui est affect��. Il n���est pas n��cessaire de mettre tous les v��hicules de la flotte priv��e en service si cette approche se r��v��le plus ��conomique. L���objectif consiste �� minimiser le co��t fixe des v��hicules, puis le co��t variable de transport et le co��t charg�� par le transporteur externe. Notre travail consiste �� appliquer la m��taheuristique de recherche adaptative �� grand voisinage sur ce probl��me. Nous comparons nos r��sultats avec ceux obtenus pr��c��demment avec diff��rentes techniques connues sur les instances de Christofides et celles de Golden.

Une heuristique de recherche �� voisinage variable pour le probl��me du voyageur de commerce avec fen��tres de temps

Nous adaptons une heuristique de recherche �� voisinage variable pour traiter le probl��me du voyageur de commerce avec fen��tres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arriv��e au d��p��t de destination. Nous utilisons des m��thodes efficientes pour la v��rification de la r��alisabilit�� et de la rentabilit�� d'un mouvement. Nous explorons les voisinages dans des ordres permettant de r��duire l'espace de recherche. La m��thode r��sultante est comp��titive avec l'��tat de l'art. Nous am��liorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les r��sultats de plusieurs instances du TSPTW pour la premi��re fois.

Development of new scenario decomposition techniques for linear and nonlinear stochastic programming

Une approche classique pour traiter les probl��mes d���optimisation avec incertitude �� deux- et multi-��tapes est d���utiliser l���analyse par sc��nario. Pour ce faire, l���incertitude de certaines donn��es du probl��me est mod��lis��e par vecteurs al��atoires avec des supports finis sp��cifiques aux ��tapes. Chacune de ces r��alisations repr��sente un sc��nario. En utilisant des sc��narios, il est possible d�����tudier des versions plus simples (sous-probl��mes) du probl��me original. Comme technique de d��composition par sc��nario, l���algorithme de recouvrement progressif est une des m��thodes les plus populaires pour r��soudre les probl��mes de programmation stochastique multi-��tapes. Malgr�� la d��composition compl��te par sc��nario, l���efficacit�� de la m��thode du recouvrement progressif est tr��s sensible �� certains aspects pratiques, tels que le choix du param��tre de p��nalisation et la manipulation du terme quadratique dans la fonction objectif du lagrangien augment��. Pour le choix du param��tre de p��nalisation, nous examinons quelques-unes des m��thodes populaires, et nous proposons une nouvelle strat��gie adaptive qui vise �� mieux suivre le processus de l���algorithme. Des exp��riences num��riques sur des exemples de probl��mes stochastiques lin��aires multi-��tapes sugg��rent que la plupart des techniques existantes peuvent pr��senter une convergence pr��matur��e �� une solution sous-optimale ou converger vers la solution optimale, mais avec un taux tr��s lent. En revanche, la nouvelle strat��gie para��t robuste et efficace. Elle a converg�� vers l���optimalit�� dans toutes nos exp��riences et a ��t�� la plus rapide dans la plupart des cas. Pour la question de la manipulation du terme quadratique, nous faisons une revue des techniques existantes et nous proposons l���id��e de remplacer le terme quadratique par un terme lin��aire. Bien que qu���il nous reste encore �� tester notre m��thode, nous avons l���intuition qu���elle r��duira certaines difficult��s num��riques et th��oriques de la m��thode de recouvrement progressif.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.