多调机环境下的树枝形铁路专用线作业车同步取送优化

围绕服务铁路枢纽地方货物流的小运转作业系统，研究一类多调机环境下的树枝形铁路专用线作业车同步取送优化问题。考虑取送顺序间隔、调机牵引能力等约束条件，以调机作业均衡为上层优化目标，以调机取送成本和货车停留成本最小化为下层优化目标建立双重目标规划模型。根据模型特点，提出融合综合关联度和异步启发式过程的两阶段融合求解方法。该方法首先基于聚类划分思想，引入综合关联度确定调机最佳数量，并对作业区进行划分，从而为调机指派作业范围。进而基于迭代寻优思路，设计异步循环启发式过程，该过程根据多调机取送车作业特点赋予循环体表述，设计循环体更新规则，引入遗传算法中的交叉与变异操作对循环体进行寻优，进而导入人工鱼群聚群行为实现循环体二次寻优，从而完成所有调机在各自作业区内取送顺序的逐步寻优过程。最后，设计实验场景对所提出的两阶段算法进行过程验证，并设计不同规模试验进行对比测试，结果表明了所提算法的有效性和较优性。     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

A new hybrid heuristic algorithm for the Precedence Constrained Production Scheduling Problem: A mining application

In this work we address the Precedence Constrained Production Scheduling Problem (PCPSP), the problem of scheduling tasks in such a way that total profit is maximized, while satisfying conditions such as precedence constraints among tasks and side constraints. A motivation for addressing this problem comes from open-pit mining industry, where the PCPSP seeks to maximize the net present value of an ore deposit by selecting the blocks (tasks) to extract, their extraction periods and their processing options, while satisfying constraints as precedences among blocks, limited availability of operational resources and maximum and/or minimum allowable concentrations of ore-grade or pollutants. Since real-world models have millions of blocks and constraints, the monolithic problem is computationally intractable. This article presents a hybrid heuristic algorithm that combines a rolling horizon decomposition with a block preselection procedure, allowing near-optimal solutions to be quickly determined. The proposed heuristic was tested on all the PCPSP instances of the MineLib library and has shown a significant improvement over the previous reported results. Moreover, a good feasible solution has been found for the instance W23, for which no solution has been previously reported.     

Multi-terminal vehicle-dispatch algorithm

This paper introduces the Multi-Terminal Sweep Algorithm, a heuristic algorithm for obtaining an approximate solution to the multiple terminal vehicle-dispatch problem. The procedure determines a set of routes by which vehicles from two or more terminals can service a collection of demand points so that the total distance traveled is kept near to the minimum. This solution also satisfies constraints on the vehicle load and on the length of each route. Application of the algorithm to eleven multiple terminal vehicle-dispatch problems shows that near-optimal solutions to large-scale problems can be found in a reasonable amount of computer time.     

A Two-Phase Exact Algorithm for MAX-SAT and Weighted MAX-SAT Problems

We describe a two-phase algorithm for MAX-SAT and weighted MAX-SAT problems. In the first phase, we use the GSAT heuristic to find a good solution to the problem. In the second phase, we use an enumeration procedure based on the Davis-Putnam-Loveland algorithm, to find a provably optimal solution. The first heuristic stage improves the performance of the algorithm by obtaining an upper bound on the minimum number of unsatisfied clauses that can be used in pruning branches of the search tree.We compare our algorithm with an integer programming branch-and-cut algorithm. Our implementation of the two-phase algorithm is faster than the integer programming approach on many problems. However, the integer programming approach is more effective than the two-phase algorithm on some classes of problems, including MAX-2-SAT problems.     

An iterated local search with multiple perturbation operators and time varying perturbation strength for the aircraft landing problem

Landing aircraft safely is an important operation that air traffic controllers have to deal with on a daily basis. For each arriving aircraft a runway and a landing time must be allocated. If these allocations can be done in an efficient way, it could give the airport a competitive advantage. The Aircraft Landing Problem (ALP) aims to minimize the deviation from a preferred target time of each aircraft. It is an NP-hard problem, meaning that we may have to resort to heuristic methods as exact methods may not be suitable, especially as the problem size increases. This paper proposes an iterated local search (ILS) algorithm for the ALP. ILS is a single solution based search methodology that successively invokes a local search procedure to find a local optimum solution. A perturbation operator is used to modify the current solution in order to escape from the local optimum and to provide a new solution for the local search procedure. As different problems and/or instances have different characteristics, the success of the ILS is highly dependent on the local search, the perturbation operator(s) and the perturbation strength. To address these issues, we utilize four perturbation operators and a time varying perturbation strength which changes as the algorithm progresses. A variable neighborhood descent algorithm is used as our local search. The proposed ILS generates high quality solutions for the ALP benchmark instances taken from the scientific literature, demonstrating its efficiency in terms of both solution quality and computational time. Moreover, the proposed ILS produces new best results for some instances.     

Multi-neighborhood based path relinking for two-sided assembly line balancing problem

This paper presents a multi-neighborhood based path relinking algorithm (MN-PR) for solving the two-sided assembly line balancing problem. By incorporating an effective local search into a path relinking framework, the proposed MN-PR algorithm integrates a number of distinguishing features, such as a multi-neighborhood based local search procedure, a dedicated path relinking operator to generate new solutions and a strategy to fix an infeasible solution generated by the path relinking procedure to a feasible one. Our proposed MN-PR algorithm is tested on a set of totally 45 public instances widely used in the literature. Comparisons with other reference algorithms show the efficacy of the proposed algorithm in terms of the solution quality. Particularly, the proposed MN-PR algorithm is able to improve the best upper bounds for one instance with 65 tasks and 326 cycle time. This paper also presents an analysis to show the significance of the main components of the proposed algorithm.     

Processing in a multi-machine batch manufacturing system with sequence dependent cost

Many workcells in batch manufacturing systems are populated with multiple, nonidentical machines that perform similar tasks. Because of the size of a batch when a job arrives, it may be uneconomical to set up two or more machines to process the same job simultaneously. An economic decision has to be made as regards which machine in the cell to assign the job. Likewise, many multi-operation jobs can be processed using one of several feasible operation sequences that may lead to different total manufacturing costs. The cost differences are the result of several factors, among which are processing time and cost dependencies between operations, fixturing requirements, and material handling requirements. When the workcell machine selection decision is considered along with the operation sequencing decision, determination of the best machine in a cell and the best operation sequence for the batch is a non-trivial task. In this paper, we address the problem of selecting the best machine within a cell and the best operation sequence for a batch when operation cost is machine and sequence dependent. The problem is modeled mathematically and solved using a heuristic algorithm. The performance of the algorithm is compared with that of an exact solution procedure.     

Revised GRASP with path-relinking for the linear ordering problem

The linear ordering problem (LOP) is an NP\mathcal{NP}-hard combinatorial optimization problem with a wide range of applications in economics, archaeology, the social sciences, scheduling, and biology. It has, however, drawn little attention compared to other closely related problems such as the quadratic assignment problem and the traveling salesman problem. Due to its computational complexity, it is essential in practice to develop solution approaches to rapidly search for solution of high-quality. In this paper we propose a new algorithm based on a greedy randomized adaptive search procedure (GRASP) to efficiently solve the LOP. The algorithm is integrated with a Path-Relinking (PR) procedure and a new local search scheme. We tested our implementation on the set of 49 real-world instances of input-output tables (LOLIB instances) proposed in Reinelt (Linear ordering library (LOLIB) 2002). In addition, we tested a set of 30 large randomly-generated instances proposed in Mitchell (Computational experience with an interior point cutting plane algorithm, Tech. rep., Mathematical Sciences, Rensellaer Polytechnic Institute, Troy, NY 12180-3590, USA 1997). Most of the LOLIB instances were solved to optimality within 0.87 seconds on average. The average gap for the randomly-generated instances was 0.0173% with an average running time of 21.98 seconds. The results indicate the efficiency and high-quality of the proposed heuristic procedure.     

考虑充电策略与电池损耗的电动汽车路径优化问题研究

针对目前研究电动物流车辆路径问题的文章未考虑电池损耗对运营成本的影响，且多在充电速率为恒定值的情况下对充电策略进行优化，本文将电动物流车辆在配送货物途中的充电时间和电池损耗成本纳入目标函数并建立了线性规划数学模型，统筹安排车辆行驶路径和充电策略使得物流企业整体运营成本最低。其次，提出了求解该问题的多阶段启发式算法MCWIGALNS。随后，通过多组算例验证了模型和算法的准确性。实验结果表明，考虑充电时间与深度放电成本的模型可以在配送距离不变或略有增加的情况下，较大幅度减少充电时间与电池损耗成本，到达降低运营成本的目的。最后，将算法实验结果与本领域已发表的成果进行比较，证明了MCWIGALNS算法对车辆路径问题具有出色的求解能力，提升了该问题理论成果的实用性。可以为物流企业电动汽车路径策略提供良好借鉴与帮助。     

单资源调度中误工问题的作业时间压缩算法

本文采用作业时间可压缩的方法来解决单资源调度中的误工问题。在安排任务处理顺序的过程中,当某个任务发生误工时,我们基于关键路径反向搜索的方法,给出了一个启发式算法,求得需要压缩的任务集,使这个误工任务的延误时间尽可能的减少,并使需要压缩的任务数目最少,最后证明了算法的有效性,并给出了一个算例。     

An iterated greedy algorithm for the flowshop scheduling problem with blocking

This paper proposes an iterated greedy algorithm for solving the blocking flowshop scheduling problem for makespan minimization. Moreover, it presents an improved NEH-based heuristic, which is used as the initial solution procedure for the iterated greedy algorithm. The effectiveness of both procedures was tested on some of Taillard’s benchmark instances that are considered to be blocking flowshop instances. The experimental evaluation showed the efficiency of the proposed algorithm, in spite of its simple structure, in comparison with a state-of-the-art algorithm. In addition, new best solutions for Taillard’s instances are reported for this problem, which can be used as a basis of comparison in future studies.     

Designing a tabu search algorithm for the two-stage flow shop problem with secondary criterion

This paper discusses the process of desigining a tabu search-based heuristic for the two-stage flow shop problem with makespan minimization as the primary criterion and the minimization of total flow time as the secondary criterion. A factorial experiment is designed to analyse thoroughly the effects of four different factors, i.e. the initial solution, type of move, size of neighbourhood and the list size, on the performance of the tabu search-based heuristic. Using the techniques of evolution curves, and response tables and response graphs, coupled with the Taguchi method, the best combination of the factors for the tabu search-based heuristic is identified, and the effectiveness of the heuristic algorithm in finding an optimal solution is evaluated by comparing its performance with the best known heuristic to solve this problem.     

基于协作的供应链优化模型

协作供应是供应链系统中的一个常见问题. 近期的一篇文献针对供应链物资需求的特 点,提出了多点协作供应的数学模型,并且给出了相应求解方法,该文称之为“启发式方法”. 现 进一步研究表明,该方法是最优的,并非是启发式的. 这一结论完善了前期研究成果,并使算法 的运用更具理论基础.     

SIMULTANEOUS BATCHING AND SCHEDULING FOR CHEMICAL PROCESSING WITH EARLINESS AND TARDINESS PENALTIES

We consider the problem of determining the allocation of demand from different customer orders to production batches and the schedule of resulting batches to minimize the total weighted earliness and tardiness penalties in context of batch chemical processing. The problem is formulated as a mixed-integer nonlinear programming model. An iterative heuristic procedure that makes use of the network nature of the problem formulation is presented to approximate an optimal solution. An algorithm polynomial in the number of batches to produce is also presented that optimally solves the problem under special cost structures.     

Single facility scheduling with dual criteria: minimizing maximum tardiness subject to minimum number of tardy jobs

This paper considers the static single machine scheduling problem with the objective of minimizing the maximum tardiness of any job subject to the constraint that the total number of lardy jobs is minimum. Based on simple dominance conditions an o(n²) heuristic algorithm is proposed to find an approximate solution to this problem. The effectiveness of the proposed heuristic algorithm is empirically evaluated by solving a large number of problems and comparing them to the optimal solutions obtained through the branch and bound algorithm.     

基于免疫遗传算法和列生成的多项目人力资源调度研究

主要研究列生成法求解带有人力资源约束的多项目多模式进度管理问题。首先根据问题建立了相应的数学模型,模型中考虑了多种约束,如项目对人员能力、水平的不同要求,目标为满足约束的条件下成本最小化,其中包含固定和可变两类成本。模型分解后,按照列生成法流程求解。由于问题的复杂性,采用启发式算法求解每个子问题:首先由基于优先原则的启发式方法给出问题的初始解,再由免疫遗传算法寻优。通过数值实验分析了算法性能、模型改进情况,不同优先原则组合对目标成本和各项目间时间分配的影响。     

An upper bound on the minimal total cost of the transportation problem with varying demands and supplies

In general cases, to find the exact upper bound on the minimal total cost of the transportation problem with varying demands and supplies is an NP-hard problem. In literature, there are only two approaches with several shortcomings to solve the problem. In this paper, the problem is formulated as a bi-level programming model, and proven to be solvable in a polynomial time if the sum of the lower bounds for all the supplies is no less than the sum of the upper bounds for all the demands; and a heuristic algorithm named TPVDS-A based on genetic algorithm is developed as an efficient and robust solution method of the model. Computational experiments on benchmark and new randomly generated instances show that the TPVDS-A algorithm outperforms the two existing approaches.     

A pairwise interchange algorithm for parallel machine scheduling

This paper considers the problem of non-preemptive scheduling n tasks on m identical parallel processors to minimize makespan for simultaneous arrivals. Based on a pairwise interchange method, an efficient algorithm ispresented which is able to give a near-optimal schedule in a short time through suitable pairwise interchange between tasks, after an initial solution is constructed. The behaviour of the algorithm is discussed. Testing results prove its high performance in comparison with available simple heuristic procedures. Finally, the algorithm is generalized for the problems of non-identical processors and non-simultaneous arrivals.