一个制造网络的最大流算法

制造网络流广泛应用于解决水源的调度及上厂的产品运输、分配、合成等问题。本文提出一个制造网络流的最大流算法。     

A Genetic Algorithm to Solve Capacity Assignment Problem in a Flow Network

Computer networks and power transmission networks are treated as capacitated flow networks. A capacitated flow network may partially fail due to maintenance. Therefore, the capacity of each edge should be optimally assigned to face critical situations—i.e., to keep the network functioning normally in the case of failure at one or more edges. The robust design problem (RDP) in a capacitated flow network is to search for the minimum capacity assignment of each edge such that the network still survived even under the edge’s failure. The RDP is known as NP-hard. Thus, capacity assignment problem subject to system reliability and total capacity constraints is studied in this paper. The problem is formulated mathematically, and a genetic algorithm is proposed to determine the optimal solution. The optimal solution found by the proposed algorithm is characterized by maximum reliability and minimum total capacity. Some numerical examples are presented to illustrate the efficiency of the proposed approach.     

求解一类无关并行机调度的遗传迭代贪心算法

以最小化最大完工时间为优化目标,建立带工单加工约束和序相关设置时间无关并行机调度问题的混合整数规划模型;考虑现实生产对求解算法在质量、收敛速度和鲁棒性等方面的较高要求,构建一种混合遗传-迭代贪心算法。在遗传变异操作中嵌入一种迭代贪心策略的破坏和构建机制,用于提高算法的种群多样性;引入基于破坏与构建操作设计而成的快速局部搜索算法来增强算法的局部开发能力;基于实际生产数据的相关特征随机生成了一系列计算案例,并通过实验说明所提新型混合算法相较于传统混合算法的优越性。     

基于改进贪婪关联算法的在线零售商优化拆单问题

针对在线零售商一地多仓及仅考虑品类拆单的场景,建立最大化整单配送模型,对单品分配方法进行研究,目的是通过改进现有算法优化配送中心中存放的单品,以进一步降低拆单率。针对贪婪订单算法和贪婪热销算法中未考虑单品间关系性的问题,结合Apriori算法,对算法进行优化设计,提出贪婪关联算法。算法应用一种新的单品分配方法寻求订单中具有强关联关系的单品,并对具有强关联关系的单品优先进行分配。实验结果表明,与贪婪订单算法和贪婪热销算法相比,改进后的算法能显著地降低拆单率,分别降低约8%和11%。     

A Heuristic Programming Algorithm for Warehouse Location

A new heuristic programming method of solving a particular type of warehouse location problem is presented. The problem is to allocate K or less facilities to N possible locations so as to service M demand centers at minimum cost. The algorithm presented is suitable for hand calculation of medium-size problems (50 × 50) or when computerized will readily solve large-scale problems of the order of (600 × 600); i.e., 600 demand centers and 600 possible locations.     

Long Division: An Example of When the Greedy Algorithm Solves a Knapsack Problem

The familiar long division procedure is recast as an application of the greedy algorithm for a Knapsack Problem. In this light it can be seen to yield the desired quotient by employing the smallest possible number of subtractions.     

A Network Flow Solution to a Rectilinear Distance Facility Location Problem

The problem of locating new facilities is considered with respect to existing facilities so as to minimize a sum of costs which consists of costs proportional to the rectilinear distances between new and existing facilities, and costs proportional to the rectilinear distances among new facilities. The location problem decomposes into two independent sub-problems, each of which is equivalent to a linear programming problem which is essentially the dual of a minimal cost network flow problem. Fulkerson's out-of-kilter algorithm provides an efficient means of solving each of the network flow problems as well as the location problem. The dual variables in each of the optimum tableaus to the two flow problems give the x and y coordinates respectively of the optimum locations of the new facilities. Several alternative approaches to solving the equivalent linear programming problems are also discussed, and some research questions are identified.     

模糊人工蜂群算法的置换流水车间调度问题求解

针对传统人工蜂群算法早熟收敛问题,基于模糊化处理和蜂群寻优的特点,提出一种模糊人工蜂群算法.将模糊输入输出机制引入到算法中来保持蜜源访问概率的动态更新.根据算法计算过程中的不同阶段对蜜源访问概率有效调整,避免算法陷入局部极值.通过对置换流水车间调度问题的仿真实验和与其他算法的比较,表明本算法可行有效,有良好的鲁棒性.     

置换流水车间调度问题的萤火虫算法求解

作为新兴的仿生群智能优化算法,分析了萤火虫算法的仿生原理,对算法实现优化过程进行了定义。针对最小化最大完工时间的置换流水车间调度问题,采用基于ROV规则的随机键编码方式和互换操作的局部搜索策略,应用萤火虫算法进行求解。通过典型实例对算法进行了仿真测试,调度结果表明了萤火虫算法求解置换流水车间调度问题的可行性和有效性,优于NEH启发式算法和粒子群算法,是解决流水线生产调度问题的一种有效方法。     

An Efficient Procedure for Implementing a Dual Simplex Network Flow Algorithm

This paper shows that for linear programming formulations of network flow problems, the nonzero components of rows of the basis inverse are identical. A simple algorithm for identifying these nonzero components is given along with a suggested data structure for implementation. The algorithm requires only one bit of storage for each node plus one additional bit. Finally we indicate how these ideas may be used in the development of a dual simplex code for network flow problems.     

DVD在线租赁问题

考虑到客户租赁DVD的具体时刻和租赁时长的概率分布,并根据其相互关联关系,对其概率分布进行修正.在对租赁过程进行详细分析的基础上,得到了保有量与DVD租赁周期的公式,建立了保有量的概率模型,根据实际数据和相关参数可以得出具体问题的数值解.此外,对不同周期下的DVD保有量进行了测算,并对不同周期分布、不同时间跨度下的保有量进行了分析. 对于给定定单租赁的优化问题,建立了具有现有存量限制条件下的0-1规划模型,并运用Lingo软件对问题进行了求解.对于给定定单的情况下的保有量优化问题,在没有限制存量的条件下,可以根据每份定单分别充分满足贪婪策略,得到用户满意度最大的DVD租赁的日需求量,进而给出日定单的保有量最优策略和满足给定用户群的分配策略.     

WRLSP: A Single-Machine, Warehouse Restricted Lot Scheduling Problem

This paper treats a single-machine, multi-product scheduling problem arising from an application in an automobile factory. The problem is to sequence the production lots of N products in a common cycle schedule to minimize the maximum storage space required by the machine's output, given constant production and demand rates, sequence-independent setup times and sharing of the storage space among the products. As the problem is strongly NP-hard, a heuristic and a branch and bound algorithm are developed for solving it. The algorithms are assessed on a set of random test problems similar in size and complexity to the original application.     

有限等待流水车间调度邻域搜索算法

针对工序间等待时间受限,目标函数为最大完工时间最短的流水车间调度问题,提出了一种动态变邻域搜索算法。算法采用工件对比较算法和贪婪插入规则,构建了初始调度;通过嵌入3-opt,2-opt实现动态变邻域搜索;并在迭代过程中加入动态禁忌策略。     

A Flow-Preserving Algorithm for the Time-Cost Trade-Off Problem

This paper introduces an iterative solution procedure for solving the time-cost trade-off problem (reducing project duration at minimum cost). The solution procedure utilizes a labeling algorithm for locating a minimal cut in the flow network provided by the Phillips and Dessouky algorithm. The minimal cut contains the set of activities to be modified in order to achieve a reduction in the project duration at minimum cost. The main contribution of the proposed procedure is in the labeling of the nodes of the network. At each iteration of the algorithm, labels and flow values are preserved for the succeeding step.     

A Primal Simplex Specialization for the Equal Flow Problem

This paper presents a primal simplex specialization for the equal flow problem. This approach is motivated by a desire to exploit the special structure of the side constraints and to maintain as much of the characteristics of pure network problems as possible. The simplex computations are discussed and a starting solution based on the subgradient optimization technique is presented. Our implementation is tested on problems with up to 1500 nodes, 6600 arcs and 600 equal flow pairs. These problems are also solved using MPSX and another specialized code for the equal flow problem. We present Computational experience which indicates that our approach is well suited for problems with up to 150 side constraints. As the number of pairs increased, MPSX with an advanced start procedure, performed better than our specialized code.     

A Branch-and-Bound Algorithm for Flow Shop Scheduling Problems

This article is concerned with the solution of the flow shop scheduling problem in which all jobs have the same machine ordering. A branch-and-bound algorithm is developed for finding the sequence of J jobs to be processed on M machines which minimizes the schedule time. Thib algorithm consists of branching and bounding processes, but without the backtracking process which guarantees optimality. The procedure employed is that in constructing a subset of feasible sequences, a node representing a partial sequence is branched. Selection of the node depends on the lower-bound concept as a decision rule. This lower bound is based on resolving the conflict of jobs on the last machine. By using this algorithm, the number of explored nodes is considerably reduced and, hence, the computational effort involved in obtaining an optimal or near-optimal solution is decreased. High quality of solutions is obtained. Computationally, this algorithm extends the size of problems that can reasonably be solved.     

基于贪心EM算法的HMRF遥感影像变化检测

提出一种基于贪心EM算法的HMRF遥感影像变化检测算法.该算法采取PCA与差值法相结合的方式来构造差分影像.首先,采用隐马尔可夫随机场( Hidden Markov Random Field,HMRF)模型描述空间上下文信息,并构造系统能量函数;然后,利用贪心EM算法克服EM算法假定混合成分数为已知、迭代结果过分依赖初...     

面向柔性作业调度问题的启发性规则改进遗传算法

对柔性作业调度问题,提出了一种启发性规则的改进遗传求解方法,此方法从启发性规则出发产生初始调度解。通过对初始调度解进行比较而产生初始种群。对初始种群通过启发规则的改进遗传算法进行优化计算,对染色体进行交叉、变异、交换和选择操作,应用启发式规则搜索关键工序并提高关键工序的交换、变异操作概率,在变异操作中利用启发式规则对变异过程加以引导,从而得到优化解。将此方法运用于一系列典型柔性调度问题进行了实验求解,并将求解结果与其他的计算方法进行了比较,表明此方法能提高求解效率,适合复杂的柔性作业调度问题求解。     

非负权图的最大二等分问题的0.488算法

本文给出了非负权图的最大二等分问题的一种近似算法,并从理论上证明了这种算法是0.488近似算法.数值实验表明这种算法能得到图的最大二等分问题近似程度很高的次优解,是一种非常有效的算法.