求同顺序m×n排序问题近优解的一个新算法——关键工件法

机械制造企业在编制生产作业计划工作中,经常遇到n个工件经m台机床加工的排序问题。即当多个工件经多台机床加工时,如何合理安排工件的加工顺序,使工件在机床上加工时,时间上不发生冲突,同时尽可能缩短加工周期。n个工件经m台机床的加工排序问题,简称为m×n排序问题。m×n排序问题是一类广泛的组合最优化问题,它的应用是极其广泛的。本文讨论的是同顺序m×n排序问题,有如下几条假设:

混合整数线性规划近优解的一种解法

所提出的混合整数线性规划的解法是利用目标函数来建立等值切割面，综合使用分支定界法、割平面法和枚举法，并在求解混合整数线性规划相应的线性规划问题时，运用两演段方法。它克服了上述方法各自单独使用在计算上的某些困难和不足。

Hierarchical multicast with inter-layer random network coding

To maximize the aggregate throughput achieved in heterogeneous networks, this paper investigates inter-session network coding for the distribution of layered source data. We define inter-layer hierarchical random linear network codes （IHRLNC）, which not only take the flexibility of intersession network coding for layer mixing but also consider the strict priority inherent in the layered source data. Furthermore, we propose the inter-layer hierarchical multicast （IHM）, which performs IHRLNC in the network such that each sink can recover some source layers according to its individu- al capacity. To determine the optimal type of IHRLNC that should be performed on each edge in IHM, we formulate an optimization problem based on 0-1 integer linear programming, and propose a heuristic approach to approximate the optimal solution in polynomial time. Simulation results show that the proposed IHM can achieve throughput gains over the layered muhicast schemes.

Improvement of Lagrangian relaxation performance for open pit mines constrained long-term production scheduling problem

Constrained long-term production scheduling problem(CLTPSP) of open pit mines has been extensively studied in the past few decades due to its wide application in mining projects and the computational challenges it poses become an NP-hard problem.This problem has major practical significance because the effectiveness of the schedules obtained has strong economical impact for any mining project.Despite of the rapid theoretical and technical advances in this field,heuristics is still the only viable approach for large scale industrial applications.This work presents an approach combining genetic algorithms(GAs) and Lagrangian relaxation(LR) to optimally determine the CLTPSP of open pit mines.GAs are stochastic,parallel search algorithms based on the natural selection and the process of evolution.LR method is known for handling large-scale separable problems; however,the convergence to the optimal solution can be slow.The proposed Lagrangian relaxation and genetic algorithms(LR-GAs) combines genetic algorithms into Lagrangian relaxation method to update the Lagrangian multipliers.This approach leads to improve the performance of Lagrangian relaxation method in solving CLTPSP.Numerical results demonstrate that the LR method using GAs to improve its performance speeding up the convergence.Subsequently,highly near-optimal solution to the CLTPSP can be achieved by the LR-GAs.

Multi-Objective Optimization of Urban Bus Network Using Cumulative Prospect Theory

Multi-objective optimization of urban bus network can help improve operation efficiency of the transit system and develop strategies for reducing urban traffic congestion in China. The work used cumulative prospect theory, currently the most influential model for decision under uncertainty,to optimize urban bus network. To achieve the research objective, the work developed the theoretical framework of urban bus network optimization, including optimization principle, optimization objectives and constraints. Furthermore, optimization objectives could comprehensively reflect expectations of passengers and bus companies from the dimension of time, space and value. It is more scientific and reasonable compared with only one stakeholder or dimension alone in the previous studies. In addition,the technique for order preference by similarity to ideal solution(TOPSIS) was used to determine the positive and negative ideal alternative. The correlations between the optimization alternatives and the ideal alternatives were estimated by grey relational analysis simultaneously. The cumulative prospect theory(CPT) was used to determine the best alternative by comparing comprehensive prospect value of every alternative, accurately describing decision-making behavior compared with expected utility theory in actual life. Finally, Case of Xi'an showed that the method can better adjust the bus network,and the optimization solution is more reasonable to meet the actual needs.

Numerical Solution to Optimal Feedback Control by Dynamic Programming Approach:A Local Approximation Algorithm

This paper considers optimal feedback control for a general continuous time finite-dimensional deterministic system with finite horizon cost functional. A practically feasible algorithm to calculate the numerical solution of the optimal feedback control by dynamic programming approach is developed. The highlights of this algorithm are: a) It is based on a convergent constructive algorithm for optimal feedback control law which was proposed by the authors before through an approximation for the viscosity solution of the time-space discretization scheme developed by dynamic programming method; b) The computation complexity is significantly reduced since only values of viscosity solution on some local cones around the optimal trajectory are calculated. Two numerical experiments are presented to illustrate the effectiveness and fastness of the algorithm.