重复性建设项目中确定关键路线的方法研究

本文提出了一种确定重复性建设项目关键路线的新方法。借助约束线,首先给出了工序间存在各种约束条件(时间和距离约束)下潜在关键点的确定方法;为处理大规模项目,进一步提出了与图示法相对应的数值算法。以此为基础,提出了确定关键工序和关键路线的具体步骤,并定义和分析了三种不同类型的关键工序。与现有的方法相比,本文提出的确定关键路线的方法更为准确,适用性更强,而且有利于调度优化目标的实现。     

Nonlinear programming without a penalty function or a filter

A new method is introduced for solving equality constrained nonlinear optimization problems. This method does not use a penalty function, nor a filter, and yet can be proved to be globally convergent to first-order stationary points. It uses different trust-regions to cope with the nonlinearities of the objective function and the constraints, and allows inexact SQP steps that do not lie exactly in the nullspace of the local Jacobian. Preliminary numerical experiments on CUTEr problems indicate that the method performs well.      

An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles

The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows.     

An applied cell mapping method for optimal control problems

From the application point of view, a series of modifications are proposed for the cell mapping method discussed in Ref. 1 for the optimal control analysis of dynamical systems. The cell order around the target set is rearranged. A set of common discriminate principles is used for the selection of the optimal one among competing control strategies of the same cost. Inequality constraints of the system are taken into account. The number of elements in the set of allowable time intervals is not prescribed, but left open. These modifications seem to make the cell mapping method more efficient for analyzing feedback systems and for obtaining their global optimal control information. The algorithms presented in this paper could broaden the application of the cell mapping approach of Ref. 1 to a wider class of engineering problems.     

A unified theory for coherent systems in reliability I. A generalization for some classic theory: Monotone binary coherent systems

Binary coherent system theory has played an important part in reliability. Its extension to (‘degradable’ or ‘multistate’ or) multinary systems has recently been considered in various papers, through various definitions. This paper lays the foundations of a unified theory for coherent systems by first giving unified arguments to apply and to investigate further binary and multinary systems. Monotone binary systems are introduced and examined by generalizing classic deterministic and probabilistic results. Applications of monotone coherence to the multinary case are proposed in a companion paper with a unified viewpoint on multinary coherent systems. As an indication, monotone constraints are defined with a partition of the component set and some total orderings imposed on the elements of the concerned partition. The discrete partition retrieves the classic theory of (free) binary coherent systems; some constraints defined from component levels lead to multinary coherent systems; some other constraints apply to systems submitted to some ‘common stresses’, e.g. the organizing system of a monotone coherent decomposition.     

求解带界约束的非线性方程组的混合方法

基于非单调技术和L-M算法, 提出了一种新的求解带界约束的非线性方程组的混合方法. 在一定条件下, 该算法具有全局收敛性. 数值试验表明该算法是有效的.     

Constraints on the fundamental topological parameters of spatial tessellations

Tessellations of that use convex polyhedral cells to fill the space can be extremely complicated, especially if they are not “facet‐to‐facet”, that is, if the facets of a cell do not necessarily coincide with the facets of that cell's neighbours. In a recent paper 15 , we have developed a theory which covers these complicated cases, at least with respect to their combinatorial topology. The theory required seven parameters, three of which suffice for facet‐to‐facet cases; the remaining four parameters are needed for the awkward adjacency concepts that arise in the general case. This current paper establishes constraints that apply to these seven parameters and so defines a permissible region within their seven‐dimensional space, a region which we discover is not bounded. Our constraints in the relatively simple facet‐to‐facet case are also new.     

Column generation for vehicle routing problems with multiple synchronization constraints

Synchronization of workers and vehicles plays a major role in many industries such as logistics, healthcare or airport ground handling. In this paper, we focus on operational ground handling planning and model it as an archetype of vehicle routing problems with multiple synchronization constraints, coined as “abstract vehicle routing problem with worker and vehicle synchronization” (AVRPWVS). The AVRPWVS deals with routing workers to ground handling jobs such as unloading baggage or refuelling an aircraft, while meeting each job’s time window. Moreover, each job can be performed by a variable number of workers. As airports span vast distances and due to security regulations, workers use vehicles to travel between locations. Furthermore, each vehicle, moved by a driver, can carry several workers. We propose two mathematical multi-commodity flow formulations based on time-space networks to efficiently model five synchronization types including movement and load synchronization. Moreover, we develop a branch-and-price heuristic that employs both conventional variable branching and a novel variable fixing strategy. We demonstrate that the procedure achieves results close to the optimal solution in short time when compared to the two integer models.     

Scheduling on same-speed processors with at most one downtime on each machine

We consider the problem of scheduling a set of independent tasks on multiple same-speed processors with planned shutdown times with the aim of minimizing the makespan. We give an LPT-based algorithm, LPTX, which yields a maximum completion time that is less than or equal to 3/2 the optimal maximum completion time or 3/2 the time that passes from the start of the schedule until the latest end of a downtime. For problems where the optimal schedule ends after the last downtime, and when the downtimes represent fixed jobs, the LPTX maximum completion time is within 3/2 of the optimal maximum completion time. In addition, we show that this result is asymptotically tight for the class of polynomial algorithms assuming that P≠NP. We also show that the bound obtained previously for a similar problem, when no more than half of the machines are shut down at the same time, for the LPT algorithm is asymptotically tight in the class of polynomial algorithms if P≠NP.