Proportionate flow-shop scheduling with rejection

In many heavily loaded manufacturing systems, managers routinely make use of outsourcing options in order to maintain reasonable Quality of Service for customers. Thus, there is a strong need to provide tools for managers to economically coordinate sourcing and scheduling decisions. Our main aim is to provide such tools for an important set of flow-shop scheduling problems where rejection (outsourcing) is allowed and processing times are machine-independent. Our scheduling problems are essentially bicriteria problems, which combine a scheduling objective and the total outsourcing cost. We study several problems which differ according to the scheduling criterion considered. Moreover, each problem is divided into four different variations depending on the way the two criteria are dealt with. For example, in one variation the two criteria are aggregated into a single objective function; in two other variations the aim consists of minimizing one criterion subject to ensuring that the value of the other criterion will not exceed a predefined threshold. From a theoretical point of view, a computational complexity classification is provided for all variations of the problems under consideration. Moreover, optimization algorithms have been constructed to solve all problem variations, and approximation schemes have been developed for solving hard variations. Those schemes enable managers to solve large instances of hard variations while controlling the maximal gap between the obtained solution and the (unknown) optimal solution.     

An analytical approach to the facility location and capacity acquisition problem under demand uncertainty

This article presents an analysis of facility location and capacity acquisition under demand uncertainty. A novel methodology is proposed, in which the focus is shifted from the precise representation of facility locations to the market areas they serve. This is an extension of the optimal market area approach in which market area size and facility capacity are determined to minimize the total cost associated with fixed facility opening, variable capacity acquisition, transportation, and shortage. The problem has two variants depending on whether the firm satisfies shortages by outsourcing or shortages become lost sales. The analytical approach simplifies the problem considerably and leads to intuitive and insightful models. Among several other results, it is shown that fewer facilities are set up under lost sales than under outsourcing. It is also shown that the total cost in both models is relatively insensitive to small deviations in optimal capacity choices and parameter estimations.     

Multi-product newsboy problem with limited capacity and outsourcing

This paper considers a multi-product newsboy system that produces multiple products for fulfilling independently uncertain demands, which share the same production capacity. To deal with possible shortage of limited capacity, productions can be outsourced. We consider two outsourcing strategies: zero lead time outsourcing, and nonzero lead time outsourcing. The structural properties and solution procedures for the profit-maximization models are developed. Numerical results are provided for obtaining some managerial insights.     

Stochastic uncapacitated hub location

We study stochastic uncapacitated hub location problems in which uncertainty is associated to demands and transportation costs. We show that the stochastic problems with uncertain demands or dependent transportation costs are equivalent to their associated deterministic expected value problem (EVP), in which random variables are replaced by their expectations. In the case of uncertain independent transportation costs, the corresponding stochastic problem is not equivalent to its EVP and specific solution methods need to be developed. We describe a Monte-Carlo simulation-based algorithm that integrates a sample average approximation scheme with a Benders decomposition algorithm to solve problems having stochastic independent transportation costs. Numerical results on a set of instances with up to 50 nodes are reported.     

Discrete stochastic location models

In this paper, we study how the two classical location models, the simple plant location problem and thep-median problem, are transformed in a two-stage stochastic program with recourse when uncertainty on demands, variable production and transportation costs, and selling prices is introduced. We also discuss the relation between the stochastic version of the SPLP and the stochastic version of thep-median.     

The one-warehouse multi-retailer problem: reformulation, classification, and computational results

We consider the one-warehouse multi-retailer problem where a warehouse replenishes multiple retailers with deterministic dynamic demands over a horizon. The problem is to determine when and how much to order to the warehouse and retailers such that the total system-wide costs are minimized. We propose a new (combined transportation and shortest path based) integer programming reformulation for the problem in addition to the echelon stock and transportation based formulations in the literature. We analyze the strength of the LP relaxations of three formulations and show that the new formulation is stronger than others. We also show that the new and transportation based formulations are equivalent for the joint replenishment problem, where the warehouse is a crossdocking facility. We extend all formulations to the case with initial inventory at the warehouse and reveal the relation among their LP relaxations. We present our computational experiments with all formulations over a set of randomly generated test instances.     

A multi-stage supply chain network design problem with in-house production and partial product outsourcing

We propose a mixed-integer linear programming model for a novel multi-stage supply chain network design problem. Our model integrates location and capacity choices for plants and warehouses with supplier and transportation mode selection, and the distribution of multiple products through the network. The aim is to identify the network configuration with the least total cost subject to side constraints related to resource availability, technological conditions, and customer service level requirements. In addition to in-house manufacturing, end products may also be purchased from external sources and consolidated in warehouses. Therefore, our model identifies the best mix between in-house production and product outsourcing. To measure the impact of this strategy, we further present two additional formulations for alternative network design approaches that do not include partial product outsourcing. Several classes of valid inequalities tailored to the problems at hand are also proposed. We test our models on randomly generated instances and analyze the trade-offs achieved by integrating partial outsourcing into the design of a supply chain network against a pure in-house manufacturing strategy, and the extent to which it may not be economically attractive to provide full demand coverage.     

A partial dual algorithm for the capacitated warehouse location problem

The Capacitated Warehouse Location Problem (CWLP) consists of the ordinary transportation problem with the additional feature of a fixed cost associated with each supplier. A supplier can be used towards meeting the demands of the customers only if the corresponding fixed cost is incurred. The problem is to determine which suppliers to use and how the customer demands should be met, so that total cost is minimised.Most of the recently published algorithms for CWLP use branch and bound based on a Lagrangian relaxation of demand constraints. Here, a partial dual of a tight LP formulation is used in order to take advantage of the properties of transportation problems. Computational results are given which show good overall performance of the algorithm, with the size of the tree search being reduced compared with previous published results.     

An extended transportation problem: a DEA-based approach

The transportation problem is an important network structured linear programming problem that arises in several contexts and that has received a great deal of attention in the literature. The existing transportation problems are limited to consideration unit of shipping cost or profit along an arc. However, in many real applications, various attributes are usually considered in a transportation problem. The current paper, proposes an extension to this problem in the presence of multiple in-commensurate inputs and outputs for each arc. The concept of relative efficiency is defined for each possible transportation plan. Two linear programming models are proposed to determine the transportation plan with the maximum efficiency. A numerical example is used to illustrate the applicability of the approach.     

A novel approach for considering layout problem in cellular manufacturing systems with alternative processing routings and subcontracting approach

In this paper a new integrated approach is presented for designing cellular manufacturing system and its inter- and intra-cell layouts. Various production factors such as part demands, alternative processing routings, operation sequences, processing times, capacity of machines, etc. are incorporated in the problem in order to extend its applicability. To increase the accuracy of the inter- and intra-cell layout design, the material handling cost is calculated in terms of the actual position of machines within the cells and regarding the dimensions of the machines and aisle distances. Also, a subcontracting approach is proposed to determine the production volume of parts within the CF and layout design process regarding the production, material handling and outsourcing costs and under demand and machine capacity constraints. To the best of our knowledge, this is the first study that addresses all these design features simultaneously. As the proposed problem is NP-hard, an efficient GA is employed to solve it. Finally, numerical examples adopted from the literature are used to verify the proposed approach.     

需求区间型运输问题的求解算法

为了便于建立与需求区间型运输问题有关的决策支持系统，本给出了一个求解需求区间型运输问题的数值算法，证明了算法的理论依据，并举例说明算法的应用，该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法有较高的计算效率。     

Transportation planning in freight forwarding companies: Tabu search algorithm for the integrated operational transportation planning problem

The integrated operational transportation planning problem extends the traditional vehicle routing and scheduling problem by the possibility of outsourcing a part of the requests by involving subcontractors. The purpose of this paper is to present the integrated planning problem and to propose an approach for solving it by a tabu search heuristic. Existing approaches from literature which discuss vehicle routing combined with outsourcing regard only one specific type of subcontracting. This paper describes and explores the complex situation where an own fleet and several types of subcontracting are used for request fulfillment. As the approach contains new aspects, unknown to the literature so far, tabu search is extended to special types of moves. On the basis of computational results the cost structure is analyzed in order to investigate the long-term planning question whether and to what extend it is profitable to maintain an own fleet.     

Quantifying the benefits of route reoptimisation under stochastic customer demands

Incorporating route reoptimisation in the management of vehicle routing operations under stochastic demands yields benefits such as lower transportation and inventory costs. Because an investment in advanced information systems is indispensable for route reoptimisation, a firm needs to estimate the likely magnitude of these benefits before making an investment decision. This study addresses this information needed by providing a framework to assess the benefits more completely than previous studies. The framework, which is the key contribution of the research, comprises a set of tractable models that together address the costs of both inventory and transportation. By accounting for key determinants of route reoptimisation's benefits, including, for example, the volatility of customer demands, the models are applicable to a broad range of vehicle routing scenarios.     

Transportation pricing of a truckload carrier

Freight transportation is a major component of logistical operations. Due to the increase in global trade, fierce competition among shippers and raising concerns about energy, companies are putting more emphasis on effective management and usage of transportation services. This paper studies the transportation pricing problem of a truckload carrier in a setting that consists of a retailer, a truckload carrier and a less than truckload carrier. In this setting, the truckload carrier makes his/her pricing decision based on previous knowledge on the less than truckload carrier’s price schedule and the retailer’s ordering behavior. The retailer then makes a determination of his/her order quantity through an integrated model that explicitly considers the transportation alternatives, and the related costs (i.e., bimodal transportation costs) and capacities. In the paper, the retailer’s replenishment problem and the truckload carrier’s pricing problem are modeled and solved based on a detailed analysis. Numerical evidence shows that the truckload carrier may increase his/her gainings significantly through better pricing and there is further opportunity of savings if the truckload carrier and the retailer coordinate their decisions.     

Integrating transportation and production: an international study case

The problem we study is inspired by the real case of Mesdan S.p.A., an Italian company worldwide leader in the textile machinery sector, which has two production units with two warehouses, one located in Italy (Brescia) and the other in China (Foshan). The critical point in this logistic system is the integration between production and transportation management, given the long distance between Brescia and Foshan. Shipments are performed by the means of different types of vehicles with different unit costs and significantly different lead times. Variable production costs, variable and fixed transportation costs and, possibly, inventory costs are charged in the objective function. Different production policies are compared. Our aim is to determine integrated policies that minimize the total cost of the system. We formulate integer linear programming models for the solution of these problems, and we solve the real instance and carry out a sensitivity analysis of the optimal solution.     

Capacitated location model with online demand pooling in a multi-channel supply chain

This paper presents a location model that assigns online demands to the capacitated regional warehouses currently serving in-store demands in a multi-channel supply chain. The model explicitly considers the trade-off between the risk pooling effect and the transportation cost in a two-echelon inventory/logistics system. Keeping the delivery network of the in-store demands unchanged, the model aims to minimize the transportation cost, inventory cost, and fixed handling cost in the system when assigning the online demands. We formulate the assignment problem as a non-linear integer programming model. Lagrangian relaxation based procedures are proposed to solve the model, both the general case and an important special case. Numerical experiments show the efficiency of our algorithms. Furthermore, we find that because of the pooling effect the variance of in-store demands currently served by a warehouse is an important parameter of the warehouse when it is considered as a candidate for supplying online demands. Highly uncertain in-store demands, as well as low transportation cost per unit, can make a warehouse appealing. We illustrate with numerical examples the trade-off between the pooling effect and the transportation cost in the assignment problem. We also evaluate the cost savings between the policy derived from the model, which integrates the transportation cost with the pooling effect, and the commonly used policy, which is based only on the transportation cost. Results show that the derived policy can reduce 1.5–7.5% cost in average and in many instances the percentage of cost savings is more than 10%.     

单机单转包商调度与外包联合优化问题的改进启发式算法

针对以总完工时间与总外包费用加权和为优化目标、总外包费用不超过给定上限的单机单转包商调度与外包联合优化问题,设计出一种改进的剔除型启发式算法。该算法通过运用动态规划技术求解新的辅助问题来获取初始外包工件集,并引入判定条件提前从初始外包工件集中剔除特定工件。为满足对总外包费用的上限约束,还利用新型的启发式筛选次序族逐一确定从当前外包工件集中剔除的工件。在仿真实验中,通过生成大量的测试算例,对比分析了改进算法与另2种已报道算法在求解质量、计算时间上的表现情况。实验结果表明所提出的改进算法在解的整体质量上具备显著的比较优势,并且能在5.6秒内完成对工件总数为1500的测试算例的求解。     

Design of mathematical models for the integration of purchase and production lot-sizing and scheduling problems under demand uncertainty

This study addresses the multi-level lot-sizing and scheduling problem with complex setups and considers supplier selection with quantity discounts and multiple modes of transportation. The present research proposes a mixed-integer linear programming (MILP) model in which the purchase lot-sizing from multiple suppliers, production lot-sizing with multiple machines and scheduling of various products of different families are accomplished at the same time. However, these decisions are not integrated in traditional environments and are taken separately. In this study, two different types of lot-sizing models called aggregated and disaggregated are developed for the problem to evaluate and compare the computational efficiency of them under deterministic and stochastic demands and provide some managerial insights. To deal with the stochastic demands, Chance-Constrained Programming (CCP) approach is applied. Based on the results of this study, the average profit of the separated (purchase from production) lot-sizing model under demand choice flexibility and stochastic demand is 24% and 22% less than the integrated model, respectively. Moreover, the results also confirm the effect of discount structure on the amount of purchases, productions, revenues and costs.     

Equitable Demand Adjustment for Infeasible Transportation Problems

We present a modelling/solution procedure for adjusting demands to obtain an ‘equitably infeasible’ solution for an infeasible transportation problem. The infeasibility may be due to total supply not being equal to total demand, or inadmissible routes (arcs). We show that the problem can be modelled and solved as a pre-emptive, multicriteria, capacitated transportation problem, whose objective is to minimize the maximum deviation between the fractional undersupply to the demand nodes or, equivalently, to minimize the fractional undersupply of the demands. Further, we show that an optimal solution can be obtained by solving either a single-criterion transportation problem (by choosing sufficiently large weights to aggregate the criteria) or a sequence of single-criterion transportation problems.     

考虑外包的单产品再制造批量决策

在已有动态批量决策问题的基础上,考虑了再制造与外包这两个因素建立了单产品的再制造批量决策模型。对考虑外包的单产品再制造批量决策问题最优解的性质进行了讨论,在此基础上利用动态规划的思想给出了时间复杂性为O(T4)的算法,并用C++实现了本算法,实验表明本算法是有效的。