Part-type selection in flexible manufacturing systems: a bicriteria approach with due dates

We studied the part-type selection problem in a Flexible Manufacturing Environment. We formulated the problem as a bicriteria mathematical programming problem where the objectives are maximisation of a number of part-types selected and minimisation of a measure of total tardiness. Taking the vector optimisation approach, we found all of the efficient solutions to the problem. The efficient set to this problem portrays the trade-off information between the two objectives. We suggest that the Decision Maker should choose one of the efficient solutions for implementation depending on the dynamics of the system. We report computational results that highlight some characteristics of the efficient solutions. We compare the quality of solutions obtained through the bicriteria model with those of a more traditional approach: maximising the weighted sum of part-types selected where the weights are assigned based on due-dates. Our results imply a strong possibility of significant improvement in due date performance by taking a bicriteria approach to the part-type selection problem.     

Scheduling production of multiple part-types in a system with pre-known demands and deterministic inactive time intervals

We introduce and formalise a scheduling problem that consists in determining an optimum policy (i.e. one that minimises total inventory holding costs) to produce n part-types using a system that is able to share its capacity at all times among these part-types and that switches between an active and an inactive state for pre-known periods of time. Consequently, when active the system must produce enough reserves to meet the demand during the inactive interval. We show that there is always a simple optimum policy in which the production of the part-types is prioritised and, provided the units are properly defined, the optimum priority ordering corresponds to a non-decreasing sequence of the unit holding costs of the part-types.     

Warm-Start Heuristic for Stochastic Portfolio Optimization with Fixed and Proportional Transaction Costs

We consider a probabilistic portfolio optimization model including fixed and proportional transaction costs. We derive a deterministic equivalent of the probabilistic model for fat-tailed portfolio returns. We develop a method which finds provably near-optimal solutions in minimal amount of time for industry-sized (up to 2000 assets) problems. To solve the mixed-integer nonlinear programming (MINLP) deterministic formulation equivalent to the stochastic problem, we design a mathematical programming-based warm-start heuristic. The tests show the computational efficiency of the heuristic which is more than an order of magnitude faster than Cplex in finding high-quality solutions.     

Dynamic lot-sizing with price changes and price-dependent holding costs

This paper proposes a new formulation of the dynamic lot-sizing problem with price changes which considers the unit inventory holding costs in a period as a function of the procurement decisions made in previous periods. In Section 1, the problem is defined and some of its fundamental properties are identified. A dynamic programming approach is developed to solve it when solutions are restricted to sequential extreme flows, and results from location theory are used to derive an O(T²) algorithm which provides a provably optimal solution of an integer linear programming formulation of the general problem. In Section 2, a heuristic is developed for the case where the inventory carrying rates and the order costs are constant, and where the item price can change once during the planning horizon. Permanent price increases, permanent price decreases and temporary price reductions are considered. In Section 3, extensive testing of the various optimal and heuristic algorithms is reported. Our results show that, in this context, the two following intuitive actions usually lead to near optimal solutions: accumulate stock at the lower price just prior to price increase and cut short on orders when a price decrease is imminent.     

物流服务供应链订单分配优化及其遗传算法

针对物流服务供应链订单分配问题中,物流服务集成商通常会按照所分配的订单价值向分包商收取一定比例交易费用的特点,设定交易费用为交易额的线性函数,构建了新的物流服务供应链订单分配优化混合整数规划模型,其优化目标为最小化交易费用、采购费用、短缺服务与延迟供给的物流能力数量。鉴于问题的NP-hard特性,设计了相应的遗传算法,并结合基于优先权的启发式规则避免了大量非法初始解的出现。实验算例表明所建立的模型能够反映物流服务供应链订单分配过程中的线性交易费用因素,其所设计的算法能够在可接受的时间内获得质量较高的满意解,并且对于大规模订单分配优化问题,遗传算法的求解时间与求解结果要优于LINGO软件。     

A stabilized column generation scheme for the traveling salesman subtour problem

Given an undirected graph with edge costs and both revenues and weights on the vertices, the traveling salesman subtour problem is to find a subtour that includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour.We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented.     

The multiple container loading cost minimization problem

In the shipping and transportation industry, there are several types of standard containers with different dimensions and different associated costs. In this paper, we examine the multiple container loading cost minimization problem (MCLCMP), where the objective is to load products of various types into containers of various sizes so as to minimize the total cost. We transform the MCLCMP into an extended set cover problem that is formulated using linear integer programming and solve it with a heuristic to generate columns. Experiments on standard bin-packing instances show our approach is superior to prior approaches. Additionally, since the optimal solutions for existing test data is unknown, we propose a technique to generate test data with known optimal solutions for MCLCMP.     

A global supply chain model with transfer pricing and transportation cost allocation

We present a model for the optimization of a global supply that maximizes the after tax profits of a multinational corporation and that includes transfer prices and the allocation of transportation costs as explicit decision variables. The resulting mathematical formulation is a non-convex optimization problem with a linear objective function, a set of linear constraints, and a set of bilinear constraints. We develop a heuristic solution algorithm that applies successive linear programming based on the reformulation and the relaxation of the original problem. Our computational experiments investigate the impact of using different starting points. The algorithm produces feasible solutions with very small gaps between the solutions and their upper bound (UB).     

A Multi-Stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation of the problem is proposed using variable disaggregation to exploit the lot-sizing substructure of the problem. The reformulation significantly reduces the LP relaxation gap of this large scale integer program. A heuristic scheme is presented to perturb the LP relaxation solutions to produce good quality integer solutions. Finally, we outline a branch and bound algorithm that makes use of the reformulation strategy as a lower bounding scheme, and the heuristic as an upper bounding scheme, to solve the problem to global optimality. Our preliminary computational results indicate that the proposed strategy has significant advantages over straightforward use of commercial solvers.     

A methodology to create robust job rotation schedules

This research proposes a methodology for developing robust job rotation schedules to reduce the likelihood of low back injury due to lifting. We consider settings that have uncertain task demands and different worker profiles in order to simulate real settings. We begin by considering deterministic versions of the problem and solve these using mathematical programming. Because mathematical programming cannot be readily applied to stochastic versions of the problem, heuristic solution methods are developed. The effectiveness of these methods is demonstrated by comparing the results with provably optimal solutions from the deterministic problems and with an enumerative approach that is applied to the stochastic version of the problem. Across the test problems, the proposed heuristics are effective at finding good job rotation solutions. The proposed methods could also be applied to solve other job rotation objectives such as maximizing productivity and reducing exposure to other work environmental factors such as excessive noise.     

Assignment problems with changeover cost

We consider some variant models, having changeover cost, of the assignment problem. In these models, multiple assignments to an operator are allowed. In addition to assignment costs, a changeover cost is incurred if an operator does one job after another is completed. Two different types of changeover costs and related two models are considered. Mathematical programming formulations are given for the models. When changeover costs are dependent on the operator but independent of the jobs and are non-negative, a linear programming model is obtained. For the case when changeover costs are dependent on the jobs, a linear integer programming formulation is obtained. We also show that, this problem is strongly NP-hard. A heuristic solution method is suggested for it. Numerical findings on the performance of the method are given.     

A single machine scheduling problem with availability constraints and sequence-dependent setup costs

We study a single machine scheduling problem with availability constraints and sequence-dependent setup costs, with the aim of minimizing the makespan. To the authors’ knowledge, this problem has not been treated as such in the operations research literature. We derive in this paper a mixed integer programming model to deal with such scheduling problem. Computational tests showed that commercial solvers are capable of solving only small instances of the problem. Therefore, we propose two ways for reducing the execution time, namely a valid inequality that strengthen the linear relaxation and an efficient heuristic procedure that provides a starting feasible solution to the solver. A substantial gain is achieved both in terms of the linear programming relaxation bound and in terms of the time to obtain an integer optimum when we use the enhanced model in conjunction with providing to the solver the solution obtained by the proposed heuristic.     

考虑泊位疏浚的连续型泊位和动态岸桥联合调度

针对集装箱码头泊位需要定期维护的实际特征,研究了泊位疏浚情况下连续型泊位和动态岸桥联合调度问题。首先,建立了一个以船舶周转时间最小为目标的整数线性规划模型;其次,针对问题特性设计了三种启发式算法。为了分析泊位疏浚对码头工作的影响并验证模型正确性和算法有效性,分别对未考虑泊位疏浚和考虑泊位疏浚两种调度情形,进行了小规模与大规模问题输入的多组测试。三种算法在小规模输入上均取得了相同于CPLEX的精确解,从而验证了算法的有效性;进一步通过对比分析这些算法在大规模输入中的运行结果,验证其有效性能。     

Solving a capacitated hub location problem

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders’ Decomposition approach outperforms the standard Benders’ Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly.     

Minimizing makespan in a two-machine flowshop scheduling with batching and release time

This paper studies two-machine flowshop scheduling with batching and release time, whose objective is to minimize the makespan. We formulate the scheduling problem as a mixed integer programming model and show that it is a strongly NP-hard problem. We derive a lower bound and develop dynamic programming-based heuristic algorithms to solve the scheduling problem. Computational experiments are carried out to evaluate the performance of the heuristic algorithms. The numerical results show that some of the heuristic algorithms can indeed find effective solutions for the scheduling problem.     

Multiple machine continuous setup lotsizing with sequence-dependent setups

We address the short-term production planning and scheduling problem coming from the glass container industry. A furnace melts the glass that is distributed to a set of parallel molding machines. Both furnace and machine idleness are not allowed. The resulting multi-machine multi-item continuous setup lotsizing problem with a common resource has sequence-dependent setup times and costs. Production losses are penalized in the objective function since we deal with a capital intensive industry. We present two mixed integer programming formulations for this problem, which are reduced to a network flow type problem. The two formulations are improved by adding valid inequalities that lead to good lower bounds. We rely on a Lagrangian decomposition based heuristic for generating good feasible solutions. We report computational experiments for randomly generated instances and for real-life data on the aforementioned problem, as well as on a discrete lotsizing and scheduling version.     

基于物料周转率与需求相关性的储位分配优化策略与算法

优化储位分配策略是加快订单拣选速度和提高仓储效率的重要前提。在实际出入库操作中,物料可能具有一定的需求相关性,如螺钉与螺母。若这些需求相关度较高的物料被安排于距离较远的货位,将大大影响其拣选出库的效率。因此,本研究考虑不同储位分配方案的影响,提出将基于物料周转率的存储策略(COI)与物料需求相关度相结合的存储策略,使得周转频率高和相关度大的物料在仓库中的位置接近,且存储于更近仓库出入口的巷道货位。由于模型的计算规模随着参数增长呈指数式增长,本研究开发出一种近似算法,并通过实验证明,相较于商业软件,本算法可更为有效得获取问题的最优或近似解。最后通过实例分析,给出不同COI系数与物料需求度偏好下该仓库的可行储位分配方案     

Two-Stage Optimization in a Transportation Problem

A study of the economic distribution of maize throughout South Africa is reported. Although the problem of minimizing total transportation costs in such a situation is a classical one, and its solution is well known, there was in this case a high degree of degeneracy in the system and thus the solution was not unique. Also, since a user is required to pay his own transportation costs, the various optimal solutions were not equivalent. A secondary problem thus arose, viz. that of selecting from these optimal solutions the one which would be fairest to all users. A heuristic and a goal programming method for solving this secondary problem are discussed.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.