Decomposition algorithms for the integrated process planning and scheduling problem

There are several algorithms to solve the integrated process planning and scheduling (IPPS) problem (i.e., flexible job shop scheduling with process plan flexibility) in the literature. All the existing algorithms for IPPS are heuristic-based search methods and no research has investigated the use of exact solution methods for this problem. We develop several decomposition approaches based on the logic-based Benders decomposition (LBBD) algorithm. Our LBBD algorithm allows us to partition the decision variables in the IPPS problem into two models, master-problem and sub-problem. The master-problem determines process plan and operation-machine assignment, while the sub-problem optimizes sequencing and scheduling decisions. To achieve faster convergence, we develop two relaxations for the optimal makespan objective function and incorporate them into the master-problem. We analyze the performance and further enhance the algorithm with two ideas, a Benders optimality cut based on the critical path and a faster heuristic way to solve the sub-problem. 16 standard benchmark instances available in the literature are solved to evaluate and compare the performances of our algorithms with those of the state-of-the-art methods in the literature. The proposed algorithm either results in the optimal solution or improves the best-known solutions in all the existing instances, demonstrating its superiority to the existing state-of-the-art methods in literature.     

PLANNING FOR TRUCK FLEET SIZE IN THE PRESENCE OF A COMMON-CARRIER OPTION

This paper considers a class of network optimization problems in which certain directed arcs must be covered by a set of cycles. Our study was motivated by a distribution planning problem of a commercial firm that had to make deliveries over several origin-destination pairs (directed arcs) and that could service any demand arc by using a vehicle in its own fleet or by paying a common carrier. The problem is to determine an optimal fleet size and the resulting vehicle routes while satisfying maximum route-time restrictions. We formulate the problem, describe some approximate solution strategies, and discuss important implementation issues.     

LOT-SIZING IN CAPACITATED MULTI-STAGE SERIAL SYSTEMS

The lot-sizing problem in capacitated multi-stage systems with a serial product structure is addressed. This is a complex optimization problem that is part of the decision set in material requirements planning (MRP) systems. The mathematical model that describes the problem uses the concept of echelon stock and includes lead times. Setup times are taken into account, which implies that the problem of finding a feasible solution is NP-Complete. This paper proposes a heuristic method that provides a production plan in order to minimize inventory, production, and setup costs. The heuristic starts from a solution for the uncapacitated problem, which is given by the sequential application of the Wagner-Whitin algorithm. Feasibility is then attempted by shifting production amounts between periods. Computational tests conducted in 1,800 instances with up to 40 components and 18 periods have shown that feasible solutions were obtained in 83.7% of the instances. For the infeasible instances, on average, the heuristic is able to find solutions with very low capacity excess. The solutions' quality is evaluated through a lower bound provided by Lagrangean relaxation and on average the gap is less than 10%.     

Solving the part families problem in discrete-parts manufacture by simulated annealing

In the production planning and control of discrete-parts manufacture, aggregation of parts into families, on the basis of similarity, is carried out to ease both long-horizon planning and short-horizon scheduling. Additional advantages are related to those of group technology (GT), such as simplifying the flow of parts and tools and reducing both set-up and production costs. The problem of formally forming part families is presented and discussed. Previous work is reviewed and assessed. Two solution approaches, one based on a location model, the other on simulated annealing, are presented and compared along with test results. The location formulation, which results in an integer programming model solved by Lagrangian relaxation, proved capable of producing solutions of excellent quality, but only for relatively small problem instances. In contrast, simulated annealing, which is a general heuristic approach to combinatorial optimization, produced solutions of comparable quality and could handle realistically large problem instances. However, careful design of the simulated annealing algorithm is crucially important. An effective design is presented.     

运输网络运量分配问题的模型及算法研究

针对我国在运量分配模型及算法方面研究比较薄弱的现状,本文对此问题进行了系统深人的研究,应用运筹学、计算机科学的新的理论和方法,建立了多目标运量分配优化模型,且在模型中,将一些重要特性考虑成运输流量的函数,从而可使分配结果更符合实际情况。同时为求解该模型,本文研究设计了鲁棒性强、高效、实用的自适应搜索算法。     

Perspective on succession planning in multiple MNCs: interview with Aparna Sharma

?Organizations are often confronted with the challenges of developing a continuous flow of functional leaders who can operate effectively in different cultural contexts. To maintain a sustainable leadership structure across different functional units, organizations need to put in place an efficient succession plan to meet any unexpected leadership void. The existing scholar practitioner literature offers limited information regarding evidence-based practices adopted by organizations for creating an effective succession planning strategy. The interview presented here is an attempt to highlight different approaches and strategies of effective succession management for ensuring leadership continuity and harnessing talent from within the organizations.     

基于公理设计和功能过剩的公共住房撮合分配方法

公共住房的合理分配是关系保障性安居工程成败及可持续发展的"生命线"。公共住房分配中缺乏科学规划和依据,既难以保障公共住房资源分配的"公平正义",也在一定程度上造成了效率缺失。本文借鉴双边匹配思想,给出了一种基于公理设计和功能过剩的公共住房撮合分配方法,构建了一个公共住房撮合分配多目标优化决策模型。文中给出的公共住房分配案例计算表明,该方法有利于提高公共住房撮合分配的科学性、合理性及正确性,具有一定的可行性和适用性。基于相关系数权重的数值模拟试验,研究进一步探讨了住房保障的发展阶段、住房保障策略与最优撮合分配结果的关系,为公共住房分配提供了一些策略:在住房保障起步和发展阶段,应当优先考虑较高的保障覆盖面,同时也应避免公共住房对保障需求过剩;在住房保障发展成熟和完善阶段,则应当注重提高住房保障的保障水平,尽力满足住房保障对象更高水平的住房改善需求。     

Planning for changes in stages of corporate development

A considerable amount of research has demonstrated how companies evolve in terms of strategy and organizational design. The evolution of firms reflects the dynamic response of companies to their changing environment. It is logical that planning must also change in response to changes in overall corporate strategy. This dynamic aspect of planning requires a different approach than planning for the continuing growth of existing businesses based on a consistent strategic outlook. This difference is illustrated by reference to two components of planning: fixed and variable. These distinctions are used to demonstrate the dynamic aspect of planning and how planning can, and should, change to accomodate changes in management strategies.     

INCORPORATING SALES FORCE PREFERENCES IN A GOAL PROGRAMMING MODEL FOR THE SALES RESOURCE ALLOCATION PROBLEM

This note presents a model for the sales territory assignment and resource allocation problem. The integer-goal-programming model includes input from the sales representatives in the form of preference values along with organizational goal values from management. The approach integrates the multiple objectiive inputs both for individual sales reprresentatives and for the organization into a single model by employing the approaches of multiattribute utility theory and multicriteria decision making. The purpose of the model is to provide a vehicle for testing various strategies and assessing the impact of those strategies on the sales representatives’utilities and the organization's goals.     

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.     

Land use planning: An optimizing model

An optimizing model for comprehensive land use planning (OPTPLAN) is described. Multiple objectives and constraints on desired growth patterns are considered simultaneously in arriving at optimal acreages of ten land use types in several regions within a county or city. Objectives are (i) minimization of conflict between different land uses, (ii) minimization of travel distance of new trips to the existing transportation network, (iii) generation of a fiscally sound plan, and (iv) minimization of environmental impact. Constraints are on each type of land use based on population and employment projections, projected mix of residential dwelling units, local commercial and institutional land needed per thousand persons, location and extent of new industries, open space requirements per thousand population, and natural resource considerations. Application of the model to Du Page County, Illinois is shown.     

Branch‐and‐Price Methods for Prescribing Profitable Upgrades of High‐Technology Products with Stochastic Demands*

This paper develops a model that can be used as a decision support aid, helping manufacturers make profitable decisions in upgrading the features of a family of high‐technology products over its life cycle. The model integrates various organizations in the enterprise: product design, marketing, manufacturing, production planning, and supply chain management. Customer demand is assumed random and this uncertainty is addressed using scenario analysis. A branch‐and‐price (B&P) solution approach is devised to optimize the stochastic problem effectively. Sets of random instances are generated to evaluate the effectiveness of our solution approach in comparison with that of commercial software on the basis of run time. Computational results indicate that our approach outperforms commercial software on all of our test problems and is capable of solving practical problems in reasonable run time. We present several examples to demonstrate how managers can use our models to answer “what if” questions.     

基于Benders分解算法的跨区互联电力系统协调规划模型

研究跨区互联电力系统的协调规划,对于提高投资效率实现更大范围的资源配置具有较强现实意义。本文首先描述多区域电力系统扩张规划问题,并建立多区域扩张规划模型,旨在寻求最优的扩容方案,以最小投入来满足多区域电力系统负荷增长需求;其次,采用Benders分解算法将多区域扩张规划问题分解为一个规划主问题和一个运行子问题,通过主子问题之间的迭代求解,获得最终的最优解;最后,对某个典型的包含7个区域的多区域电力系统进行模拟仿真,验证了本文所构建模型及算法的有效性。     

Designing an effective financial planning and control system

This article addresses the problems to be found in the design of financial planning and control systems. The primary purpose of an effective planning and control system is to minimize the possibility of management crises and to accomplish this, management must plan for the development of such systems as it would plan for plant expansion or new product development, recognizing the changing needs of the system as the company evolves.     

An integer programming method for the design of multi-criteria multi-action conservation plans

The design of conservation management plans is a crucial task for ensuring the preservation of ecosystems. A conservation plan is typically embodied by two types of decisions: in which areas of a given territory it will be implemented, and how actions against threats will be deployed across these areas. These decisions are usually guided by the resulting ecological benefit, their spatial effectiveness, and their implementation cost.In this paper, we propose a multi-criteria optimization framework, for modeling and solving a mixed integer programming characterization of a multi-action and multi-species conservation management design problem. The optimization tool seeks for a management plan that maximizes ecological benefit and minimizes spatial fragmentation, simultaneously, while ensuring an implementation cost no greater than a given budget.For showing the effectiveness of the methodology, we consider a case study corresponding to a portion of the Mitchell river catchment, located in northern Australia, where 31 freshwater fish species are affected by four threats.The attained results show how the methodology exploits the trade-offs among the ecological, spatial and cost criteria, enabling decision-makers to explore and analyze a broad range of conservation plans. Selecting conservation plans in a more informed way allows to obtain the best outcomes from a strategic and operational point of view.     

Decentralized planning with an interdependent marketing-production system

An interdependent marketing-production planning model based on control theory is described. The interdependent model is a composition of the Vidale-Wolfe model relating advertising rates to sales rates, and the Holt, Modigliani, Muth & Simon (HMMS) production inventory planning model. An overall optimal marketing-production plan is identified using the interdependent model. This overall optimal plan (resulting from centralized planning) is then used as a reference point to measure the effectiveness of decentralized planning approaches. It is found that in some cases almost no coordination is necessary, in some cases the use of a transfer price leads to good decentralized planning, and in other cases centralized planning must be employed to achieve good results. Several examples are presented to illustrate the cases in which decentralized planning does and does not work well.     

Finding paths with minimum shared edges

Motivated by a security problem in geographic information systems, we study the following graph theoretical problem: given a graph G, two special nodes s and t in G, and a number k, find k paths from s to t in G so as to minimize the number of edges shared among the paths. This is a generalization of the well-known disjoint paths problem. While disjoint paths can be computed efficiently, we show that finding paths with minimum shared edges is NP-hard. Moreover, we show that it is even hard to approximate the minimum number of shared edges within a factor of $2^{\log^{1-\varepsilon}n}$ , for any constant ε>0. On the positive side, we show that there exists a (k?1)-approximation algorithm for the problem, using an adaption of a network flow algorithm. We design some heuristics to improve the quality of the output, and provide empirical results.     

Two-level network design with intermediate facilities: An application to electrical distribution systems

We consider the two-level network design problem with intermediate facilities. This problem consists of designing a minimum cost network respecting some requirements, usually described in terms of the network topology or in terms of a desired flow of commodities between source and destination vertices. Each selected link must receive one of two types of edge facilities and the connection of different edge facilities requires a costly and capacitated vertex facility. We propose a hybrid decomposition approach which heuristically obtains tentative solutions for the vertex facilities number and location and use these solutions to limit the computational burden of a branch-and-cut algorithm. We test our method on instances of the power system secondary distribution network design problem. The results show that the method is efficient both in terms of solution quality and computational times.     

Integrating commercial and residential pickup and delivery networks: A case study

This paper presents a strategic analysis of the network design problem faced by pickup and delivery companies operating in metropolitan areas and serving two or more classes of customers. The focus is on a division that treats commercial and residential customers separately, a situation motivated by their respective geographic densities and the size and frequency of their demand. In constructing driver work areas, it is necessary to take into account expected demand, vehicle capacity, time on the road, and the aspect ratio of the individual territories. This leads to a capacitated clustering problem with side constraints that has been the subject of intense research over the last decade.     

Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays

We revise existing and introduce new mixed-integer programming models for the Multiprocessor scheduling problem with communication delays. The basis for both is the identification of two major modeling strategies one of which can be considered ordering-based, and the other assignment-based. We first reveal redundancies in the encoding of feasible solutions found in present formulations and discuss how they can be avoided. For the assignment-based approach, we propose new inequalities that lead to provably stronger continuous relaxations and better performance in practice. Moreover, we derive a third, novel modeling strategy and show how to more compactly linearize assignment formulations with quadratic constraints. In a comprehensive experimental comparison of representative models that reflect the state-of-the-art in terms of strength and size, we evaluate not only running times but also the obtained lower and upper bounds on the makespan for the harder instances of a large scale benchmark set.