供应链中生产和运输协调调度问题初探

提出了解决供应链中生产和航空运输协调调度问题的理论框架.基于对生产调度和航空运输调度彼此制约关系的分析,协调调度问题被分解为两个子调度问题.建立了航空运输子调度问题的整数规划模型,并证明了该问题为NP完全问题.提出了基于倒排调度方法(backward scheduling method)的调度算法解单机生产调度子问题.     

An exact penalty function method for optimising QAP formulation in facility layout problem

A quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout problem (FLP) is to increase a system’s operating efficiency by reducing material handling costs, which can be measured by interdepartmental distances and flows. The QAP-formulated FLP can be viewed as a discrete optimisation problem, where the quadratic objective function is optimised with respect to discrete decision variables subject to linear equality constraints. The conventional approach for solving this discrete optimisation problem is to use the linearisation of the quadratic objective function whereby additional discrete variables and constraints are introduced. The adoption of the linearisation process can result in a significantly increased number of variables and constraints; solving the resulting problem can therefore be challenging. In this paper, a new approach is introduced to solve this discrete optimisation problem. First, the discrete optimisation problem is transformed into an equivalent nonlinear optimisation problem involving only continuous decision variables by introducing quadratic inequality constraints. The number of variables, however, remains the same as the original problem. Then, an exact penalty function method is applied to convert this transformed continuous optimisation problem into an unconstrained continuous optimisation problem. An improved backtracking search algorithm is then developed to solve the unconstrained optimisation problem. Numerical computation results demonstrate the effectiveness of the proposed new approach.     

A SINGULAR-ARC APPROXIMATION TO A DYNAMIC SAILPLANE FLIGHT PATH OPTIMIZATION PROBLEM

A dynamic sailplane performance problem is investigated using optimal control theory. The problem is to minimize the total flight time between successive thermals subject to zero altitude loss. From the original nonlinear optimal control problem, a singular linear/quadratic problem is derived and solved.

A relationship between the original optimal control problem and a certain parameter optimization problem is explored, and it is shown that the solution to this parameter optimization provides a lower bound for the minimum flight time of the original optimal control problem. The parameter optimization solution is adopted as the reference trajectory for the linear/quadratic problem. Finally, the linear/quadratic problem is shown to provide a good approximation to the original optimal control problem at a small fraction of the computing cost.     

基于遗传算法的高校教室调度问题

对高校教室调度问题进行研究,能使教室和课程达到一种合理的优化配置。类似问题的研究在制造业或生产系统中都占有非常重要的地位。研究首先采用三元组方式,将教室调度问题描述为一类具有机器适用限制的并行多机问题,以最小化Cmax（即集中时间提高教室利用效率）和滞后时间总和为调度目标,建立了对应的数学模型。根据问题的特性,设计了包含分派规则和遗传算法的启发式调度算法求解该类问题。研究结合问题特性在编码,个体适应度函数,交叉及变异等方面进行了设计。以实例分析验证了所设计算法的可行性和有效性。     

An improved approach for determination of index positions on CNC magazines with cutting tool duplications by integrating shortest path algorithm

Optimisation of automatic tool changer (ATC) indexing problem, where cutting tools are allocated to the stations on a turret magazine of a CNC machine, is one of the challenging problems in machining. The aim of the problem is to minimise the total indexing time of ATC. This problem becomes even more challenging if duplication of cutting tools is allowed and a bidirectional ATC is used. The problem has a unique feature which has not been stressed yet by other researchers, that is, although ATC indexing (master problem) is the main optimisation problem, objective function evaluation of this problem is a standalone optimisation problem (sub problem) indeed. Although an approximation algorithm does not guarantee optimality for the master problem, the subproblem must be solved optimally; otherwise, deficiencies arising from ill-defined objective function might be encountered. Considering this interesting future, a novel methodology, which employs a shortest path algorithm, is developed. Thus, the subproblem of this complicated problem can be optimally solved. Moreover, two metaheuristics, based on threshold accepting and descent first improvement greedy methodologies, are proposed for generating efficient solutions. Finally, several benchmarking instances are generated and solved to test the proposed algorithms.     

基于TRIZ理论的套袋机套袋装置优化设计

目的解决现有套袋机套袋装置在套袋过程中薄膜内袋容易产生折角的问题。方法利用TRZI理论中功能模型及因果链分析对初始问题进行全面分析,找到根本问题后,再将根本问题转化为TRIZ问题模型,然后利用TRIZ中解决问题的工具找到多个解决方案模型,并对方案模型进行可用性评估。结果将评估所得的最优方案进行实施,薄膜内袋折角的问题被解决,双层袋合格率达到99.5%。结论利用TRIZ理论中的一系列工具对薄膜内袋折角问题进行转化,建立了解决方案模型,选取了最优方案进行实施,成功解决了薄膜内袋折角问题。     

Surrogate Duality Based Method for Contact Problems

We present a numerical method based on surrogate duality to solve contact problems in elasticity. The primal optimization problem arising from the contact problem is converted to a corresponding dual problem using surrogate duality. An explicit dual formulation for the surrogate dual problem is obtained on some certain conditions, and a Karmarkar's interior point based method is introduced to solve the explicit surrogate dual problem. Numerical examples including some quadratic programming problems with dense matrices and one elastic contact problem are solved using the present method to show its feasibility and efficiency.     

Order batching in walk-and-pick order picking systems

This paper investigates the order-batching problem both as a theoretical problem, including its special variants, and as a practical problem, with possible heuristic solution procedures. It shows that certain special cases or variants of the order batching problem are solvable, while other cases of the problem are NP-hard. It also develops a new Mixed-Integer Programming (MIP) model to obtain near-exact solutions to the problem. The MIP provides good lower and upper bounds to the problem, which prove useful in the investigation of the heuristic solution procedures. The paper identifies and modifies slightly the order batching heuristic, which shows the strongest results in the numerical experiments. Although good solutions are obtained with this particular heuristic, the results indicate that it is computationally intensive. Furthermore, solutions obtained through the MIP model suggest there is still room to obtain even better solutions to the problem via heuristic procedures, although the challenge is to do so without further increasing the computational burden.     

Surrogated Linear Programming

This paper deals with the development of a completely different technique for solving the linear programming (LP) problem. The general LP problem is replaced by an LP problem having a single constraint called the surrogated linear programming (SLP) problem. The SLP problem retains the same objective function, but is constrained by a convex combination of the original constraints. A special equivalency relationship is derived between the general problem and the surrogated problem in route to the final computational algorithm. The technique is not subject to round off error propagation and has promise for savings in computation time.     

带有界约束非凸二次规划问题的整体优化方法

通过研究带有界约束非凸二次规划问题，给出了求解该问题的整体最优 解的分枝定界方法及其收敛性，提出了定界的紧，松驰策略，把球约束二次规划问题作为子问题来确定原问题的整体最优值下界和上界，应用分枝定界方法达到了对原问题的求解。     

Heuristics for the plate-cutting traveling salesman problem

In this paper we present a new problem that arises when parts are cut from large plates of metal or glass. We call this problem the plate-cutting traveling salesman problem (P-TSP) because it requires the determination of a minimum-length tour such that exactly one point must be visited on each of a number of given polygons. We present a mathematical formulation of the problem and show that the problem is a variation of the well-known traveling salesman problem. We examine the problem when the order in which parts are to be cut is known. For this problem we present a Lagrangean decomposition of the problem and develop lower bounds and heuristics based on this decomposition. Computational testing on problems with 5-40 polygons reveals that the heuristics give fairly good solutions. When the order in which polygons are to be cut is known, the heuristic solutions are within 3-4% of the optimal. The decomposition-based heuristics are embedded in a variable r-opt heuristic for the overall problem.     

Stress intensity solutions for the interaction between a hole edge crack and a line crack

The principle of superposition is used to solve the problem and the original problem is converted into two particular hole edge crack problems. The remote stresses are applied at infinity in the first problem. Meantime, a dislocation distribution is assumed outside the hole contour in the second problem. Singular integral equation is proposed for the solution of the second problem, in which the right hand side of the integral equation is obtained from the solution of the first problem. The first problem as well as the elementary solution of the second problem are solved by means of the rational mapping approach. Finally, numerical examples with the calculated results of stress intensity factors are presented.     

改进的单亲遗传算法求解倒垛问题

针对仓储物流中常常遇到的倒垛问题进行了分析,建立了0-1非线性整数规划模型,根据模型特点将其归结为具有问题特征的可扩展广义指派问题,该问题具有NP-难的性质,因此获得较大规模最优解是不可能的或是非常困难的.为了求解此问题,本文设计了一种特殊序号编码方式的单亲遗传算法,同时为了保持群体多样性,嵌入了启发式规则进行扰动.仿真算例表明改进后的算法较传统的遗传算法更具有效性.     

Balancing transfer lines using Benders decomposition and ant colony optimisation techniques

In this paper, we investigate a transfer line balancing problem in order to find the line configuration that minimises the non-productive time. The problem is defined at an auto manufacturing company where the cylinder head is manufactured. Technological restrictions among design features and manufacturing operations are taken into consideration. The problem is represented by an integer programming model that assigns design features and cutting tools to machining stations, and specifies the number of machines and production sequence in each station. Three algorithms are developed to efficiently solve the problem under study. The first algorithm uses Benders decomposition approach that decomposes the proposed model into an assignment problem and a sequencing problem. The second algorithm is a hybrid algorithm that mixes Benders decomposition approach with the ant colony optimisation technique. The third algorithm solves the problem using two nested ant colonies. Using 15 different problem dimensions, we compare results of the three algorithms in a computational study. The first algorithm finds optimal solutions of small problem instances only. Second and third algorithms demonstrate optimality gaps less than 4.04 and 3.8%, respectively, when compared to the optimal results given by the first algorithm. Moreover, the second and third algorithms are very promising in solving medium and large-scale problem instances.     

A nested column generation algorithm to the meta slab allocation problem in the steel making industry

This paper addresses one of the key operational decision problems in the steel industry which is related to the allocation of orders to stock materials in the surplus inventory. The meta slab allocation problem can be stated as the ‘multi-stage multiple knapsack problem’ where the problem is to design slabs using orders with similar properties (the first stage) and allocating these designed slabs into the existing meta slabs in the inventory yard (the second stage). The objective of the problem is to maximise the allocated order weights in slabs and meta slabs. For the given problem, we propose a column generation algorithm, where a column in the master problem represents meta slabs and the sub problem is to design ‘bins’, here slabs with the given orders. The sub problem itself also becomes a multiple knapsack problem and we proposed a practical set-partitioning heuristic. The proposed algorithm was tested with daily operation data given from an integrated steel company in the Asia Pacific. The computational results showed that the proposed heuristic solved the real instances pretty well. The proposed algorithm was successfully deployed to the integrated steel mill.     

Multicriteria fractional programming — an approach by means of conjugate functions

This paper deals with multicriteria fractional problems. Since this problems in general are not convex, the basic problem will be transformed into a convex optimization problem by using an extension of the conception of Dinkelbach to vector optimization. It will be formulated a dual problem to the transformed optimization problem, where conjugate functions are used. There will be proved strong and converse duality theorems with conclusions to basic fractional problem.     

A gradient search and column generation approach for the build–pack planning problem with approved vendor matrices and stochastic demand

We study a production planning problem of product assembly with random demand, where the customers choose their preferred suppliers for pairs of inter-dependent components through the approved vendor matrix. The problem is to develop production plans that minimise the expected total shortage and holding costs while observing the matrix restrictions and limited component supplies. We provide a mathematical programming formulation of the problem with a large number of decision variables, whose cost function is the solution of a parametric stochastic transportation problem. We present a gradient-based interior-point approach to solve this problem where the gradient is estimated by the shadow price from the solution of such a transportation problem. A column generation scheme is integrated into the approach to handle the large problem issue. Computational results show that our algorithm significantly improves the computational time when compared with the approach without column generation. In addition, we also discuss some extensions of the basic problem to the multi-period rolling horizon case.     

Conceptual design optimization of rectilinear building frames: A knapsack problem approach

This article presents an automated technique for preliminary layout (conceptual design) optimization of rectilinear, orthogonal building frames in which the shape of the building plan, the number of bays and the size of unsupported spans are variables. It adopts the knapsack problem as the applied combinatorial optimization problem, and describes how the conceptual design optimization problem can be generally modelled as the unbounded multi-constraint multiple knapsack problem. It discusses some special cases, which can be modelled more efficiently as the single knapsack problem, the multiple-choice knapsack problem or the multiple knapsack problem. A knapsack contains sub-rectangles that define the floor plan and the location of columns. Particular conditions or preferences for the conceptual design can be incorporated as constraints on the knapsacks and/or sub-rectangles. A bi-objective knapsack problem is defined with the aim of obtaining a conceptual design having minimum cost and maximum plan regularity (minimum structural eccentricity). A multi-objective ant colony algorithm is formulated to solve the combinatorial optimization problem. A numerical example is included to demonstrate the application of the present method and the robustness of the algorithm.     

Integrated order selection and production scheduling under MTO strategy

We consider an integrated order selection and production scheduling problem where a make-to-order (MTO) manufacturer has to select a subset of the orders to process so as to maximise the total profit, and sequence-dependent setup times and costs are incurred between the manufacturing of different classes of products. The problem is formulated as the resource-constrained profitable tour problem (RCPTP) where many variants of the traveling salesman problem (TSP) are its special cases. We model the problem as an integer program and develop an efficient algorithm to solve the problem. Computational results show the efficiency as well as effectiveness of the algorithm. The benefit of the integration is shown and managerial insights are discussed with the computational experiments as well.     

Multi-objective meta-heuristics to solve three-stage assembly flow shop scheduling problem with machine availability constraints

In this paper, a three-stage assembly flow shop scheduling problem with machine availability constraints is taken into account. Two objectives of minimising total weighted completion times (flow time) and minimising sum of weighted tardiness and earliness are simultaneously considered. To describe this problem, a mathematical model is presented. The problem is generalisation of three-machine flow shop scheduling problem and two-stage assembly flow shop scheduling problem. Since these problems are known to be NP-hard, the considered problem is also strongly NP-hard. Therefore, two multi-objective meta-heuristics are presented to efficiently solve this problem in a reasonable amount of time. Comprehensive computational experiments are performed to illustrate the performance of the presented algorithms.