Improved Approximation Bounds Via Problem Independent Linear Programming Modeling
Federico Della Croce, Politecnico di Torino, Italy
Iterated Local Search: Applications and Extensions
Helena Ramalhinho Lourenço, Universitat Pompeu Fabra, Spain
Architecture-based Method for Enterprise Transformation
Ronald Giachetti, Naval Postgraduate School, United States
Improved Approximation Bounds Via Problem Independent Linear Programming Modeling
Federico Della Croce
Politecnico di Torino
Italy
![]()
Brief Bio
Federico Della Croce is a Full Professor of Operations Research at the Department of Management and Production Engineering of Politecnico di Torino, Italy. He holds a MS in Computer Science and Automation and a PhD in Operations Research both from Politecnico di Torino. He is member of the Italian OR Society (AIRO) since 1990. His main research interests concern exact, heuristic and approximation algorithms for general combinatorial optimization problems, with emphasis on Scheduling. He has published more than 70 papers on international journals such as Computers and Operations Research, Discrete Applied Mathematics, European Journal of Operational Research, INFORMS Journal on Computing, Journal of Scheduling, Operations Research, Operations Research Letters, Theoretical Computer Science and others plus 3 textbooks on Operations Research and a divulgative book on Sudoku. He has been involved in different research projects and consulting for firms in the area of Operations Research and Logistics and holds two international patents originated from some of these projects. From 2004 to 2015 he was member of the Directive Council of the Department of Control and Computer Engineering. From 2012 to 2015 he was Head of the Department of Control and Computer Engineering and member of the Senate of Politecnico di Torino. He is currently member of the Editorial Board of the European Journal of Operational Research and of Computers and Operations Research.
Abstract
We discuss how Problem Independent Linear Programming Modeling can be used to derive approximation bounds for Combinatorial Optimization (CO) Problems and apply this approach to two standard CO fields such as scheduling and packing. We first tackle problem P || Cmax where the goal is to schedule n jobs on m identical parallel machines in order to minimize the makespan. We revisit the famous Longest Processing Time (LPT) rule providing new insights on the LPT properties and discuss the worst case performance of a slight modification of LPT that manages to improve the longstanding LPT approximation bound. By generalizing the proposed LPT revisiting, we also obtain a simple heuristic that strongly outperforms LPT on a large set of benchmark instances. We consider then the 0/1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed afterwards. The goal is to maximize the sum of the profits over the whole time horizon. We prove the tightness of some approximation ratios of a general purpose algorithm already available in the literature. Also, we add the mild and natural assumption that each item can be packed in the first time period. Correspondingly, we provide algorithms with improved approximation bounds for the cases with two and three periods, respectively.
Iterated Local Search: Applications and Extensions
Helena Ramalhinho Lourenço
Universitat Pompeu Fabra
Spain
![]()
Brief Bio
Helena Ramalhinho Lourenço is a Full Professor at the Economics and Business Department at the University Pompeu Fabra, Barcelona, Spain. She has a B.A. and Master degree in Statistics and Operations Research from the University of Lisbon, Portugal, and a Ph.D. in Operations Research from Cornell University, New York, USA. She has been involved in different research projects and consulting for firms in the area of Operations Research and Logistics. Helena has published several articles in prestigious international scientific journals and has presented her work at international congresses and conferences. Helena teaches at various undergraduate, master’s and PhD`s programs. She is currently the director of the Business Analytics Research Group and a researcher at the Center for Operational Research at the University of Lisbon. Her research interests include Operations Research, Scheduling, Combinatorial Optimization, Metaheuristics, Iterated Local Search, Heuristic Search Optimization, Vehicle Routing, Job-Shop Scheduling, Supply Chain Management, Logistics, Production and Operations Management.
Abstract
Iterated Local Search (ILS) is a conceptually simple and efficient well-known Metaheuristic. The main idea behind ILS is to drive the search not on the full space of all candidate solutions but on the solutions that are returned by some underlying algorithm; typically, local optimal solutions obtained by the application of a local search heuristic. This method has been applied to many different optimization problems having more than 9,000 entries in Google Scholar. In this talk, we will review briefly the ILS method emphasizing the extensions of ILS. We will describe three relevant types of extensions: the hybrid ILS approaches combining ILS with other metaheuristics and/or exact methods; the SimILS (Simulation+ILS) to solve Stochastic Combinatorial Optimization Problems; the MoILS to solve Multiobjective Combinatorial Optimization. We will discuss the advantages and disadvantages of these extensions and present some applications, including real ones in areas like Supply Chain Management, Economic Development or Health Care. Finally, future research topics will be presented.
Architecture-based Method for Enterprise Transformation
Ronald Giachetti
Naval Postgraduate School
United States
![]()
Brief Bio
Dr. Ronald E. Giachetti, is the Chair and Professor of Systems Engineering at the Naval Postgraduate School (NPS) in Monterey, California. He teaches and conducts research in the design of enterprise systems, systems modeling, and system architecture. He has published over 50 technical articles on these topics including a textbook on the Design of Enterprise Systems: Theory, Methods, and Architecture. At the Naval Postgraduate School he leads the systems engineering department consisting of 45 faculty and staff serving 450 students in resident and distance learning programs. In addition to managing the department, he teaches courses in system of systems engineering and system architecture. He is internationally known for his work in enterprise systems, having lectured in Colombia, Peru, Mexico and other countries, participating in the National Research Foundation of Chile, and as a member of IFAC’s technical committee on enterprise integration. Prior to joining NPS, he was an Associate Professor of Industrial and Systems Engineering at Florida International University in Miami, FL. At FIU he developed and led the MS in Information Systems program and actively taught in external programs in Jamaica, Mexico, Colombia, and Peru. He has conducted $1M in externally funded research for the Navy, NSF, US Army, US Air Force, Royal Caribbean Cruise Lines, Carnival Cruise Lines, and other Florida companies. He was a National Research Council postdoctoral researcher in the Manufacturing Systems Integration Division at the National Institute of Standards and Technology (NIST) in Gaithersburg, MD. He earned a Ph.D. in Industrial Engineering from North Carolina State University in Raleigh, NC in 1996; a MS in Manufacturing Engineering from Polytechnic University in Brooklyn, NY in 1993; and a BS in Mechanical Engineering from Rensselaer Polytechnic Institute in Troy, NY in 1990.
Abstract
This talk views the planning of enterprise transformation as a project portfolio management problem such that the enterprise must determine a transformation plan to achieve its vision of the target enterprise architecture. Planning enterprise transformation is difficult in part due to the external and internal uncertainty faced by the organization as well as the changes that can be expected as the enterprise undergoes transformation. This calls for an adaptive approach to defining the transformation plan and to executing it. This paper presents an integrated model and method to identify a project portfolio to realize the enterprise transformation. A stochastic optimization model captures and values management’s flexibility in planning enterprise transformation. To derive the project portfolio, an iterative algorithm using Monte Carlo simulation is used to generate a plan for executing the projects necessary to realize the transformation vision. A case study of a defense contractor illustrates the method. The result is a method and model to help plan and manage enterprise transformation.