约束满足自适应神经网络求解车间调度问题

提出一种基于约求满足的自适应神经网络方法求解车间作业调度问题。在该算法中,神经网络在运行过程中能够根据问题的约束类型、约束满足情况、启发式规则的选择来自适应调节神经元之间的连接权值,从而求得问题的可行解。仿真实验证明了算法的有效性。     

灾变遗传算法求解带时间窗的车辆调度问题

提出一种可以有效求解带时间窗的车辆调度问题的灾变遗传算法.遗传算法作为一种高效的启发式算法被用于解决这类组合优化问题,但是该算法存在过早收敛、易陷入局部最优等缺陷.针对此问题,在搜索过程中采用灾变算子使遗传算法跳出局部最优,并针对车辆调度问题设计一种可以直接产生可行解的交叉算子,避免染色体交叉过程中产生不可行的子代.通过仿真算例验证了所提出的算法求解带时间窗的车辆调度问题的有效性;通过与标准遗传算法、改进遗传算法和粒子群算法的比较,进一步验证了灾变遗传算法在优化性能以及算法鲁棒性方面的优势.     

求解混合流水车间调度问题的一种遗传算法

由于高度的计算复杂性(NP-hard问题),混合流水车间调度问题很难求得最优解,启发式算法和智能优化算法(如遗传算法)求解此类问题的近优解的有效性和实用性已被证实。该文提出了一种基于遗传算法的求解方法,在由染色体转换成可行调度的过程中引入工件插入方法,同时设计了一种新的交叉算子。通过大量的数值计算表明,该算法的优化质量大大优于传统的遗传算法和NEH启发式算法。     

用约束满足自适应神经网络和有效的启发式算法解Job-shop调度问题

提出一种用约束满足自适应神经网络结合有效的启发式算法求解Ｊｏｂ－ｓｈｏｐ调度问题．在混合算法中,自适应神经网络具有在网络运行过程中神经元的偏置和连接权值自适应取值的特性,被用来求得调度问题的可行解,启发式算法分别被用来增强神经网络的性能、获得确定排序下最优解和提高可行解的质量．仿真表明了本文提出的混合算法的快速有效性．     

基于约束满足方法求解炼钢—连铸生产调度问题

针对各阶段均有并行机的炼钢—连铸生产调度问题,建立了问题的约束满足模型．通过分析炼钢—连铸调度问题特点,将其归结为最小化操作开工时间偏移的调度问题．在求解过程中,首先用变量选择和值选择启发式方法构造时间可行的初始调度,然后应用冲突检查算法检测资源冲突，基于回跳的后向修剪组合算法修复冲突,直至得到一个一致性的最终解．数据实验表明本文提出的方法是有效的.     

用约束满足自适应神经网络和有效的启发式算法解Job—shop调度问题

提出一种用约束满足自适应神经网络结合有效的启发式算法求解Ｊｏｂ－ｓｈｏｐ调度问题,在混合算法中,自适应神经网络具有在网络运行过程中神经元的偏置和连接权值自适应取值的特性,被用来求得调度问题的可行解,启发式算法分别和来增强神经网络的性能,获得确定排序下最优解和提高可行解的质量。仿整表明了本文提出的混合算法的快速有效性。     

一类Job- shop 车间生产计划和调度的集成优化

讨论一类Job—shop车间的生产计划和调度的集成优化问题，给出了该问题的非线性混合整数规划模型，并采用混合遗传算法进行求解。该模型利用调度约束来细化生产计划，以保证得到可行的调度解。在混合算法中，利用启发式规则来改善初始解集，并采用分段编码策略将计划和调度解映射为染色体。算例研究表明，该算法对求解该类问题具有很好的效果。     

用于炼油厂原油库存调度的混合模拟退火算法

现有的数学规划法在解决原油库存调度优化问题时存在着组合爆炸的问题,是阻碍调度优化实用化的主要原因。由于实践中往往只要求快速地获得一个较好解,因此作为启发式算法之一的模拟退火法,在解决调度问题的实用化方面具有很大的优越性。但由于模拟退火法较适于处理无约束的整数规划问题,而在原油库存调度优化模型中却存在着大量的实数约束,所以在其中直接应用模拟退火法比较困难。该文将模拟退火法与线性规划法相结合,以前者调动后者,后者为前者提供可行解判据,构成了一种优化混合算法。在将混合算法应用于原油库存调度问题时,该文采用了特定的编码方式,使各控制变量在随机变化时尽量满足相关的约束条件,从而避免了许多无效解的产生。实例计算结果表明,同传统的混合整数线性规划方法相比,这种混合算法可以快速地给出优化解,其优化值与全局最优值差别不大,表明混合算法可以更好地解决实际原油调度问题。     

汽车装配线生产计划与调度的集成优化方法

为提高汽车装配线的生产效率,优化资源配置,研究了汽车装配线生产计划和调度的集成优化问题,给出了该问题的混合整数规划模型.利用分枝定界算法和单纯型法求得问题的粗生产计划.通过将模拟退火算法和快速调度仿真相结合,探讨了一种新的启发式算法.然后基于已求得的粗生产计划,针对三种不同寻优组合论述了该算法的实现.将该算法应用于实际算例,仿真结果表明该算法对求解此类问题有着很好的效果.     

基于混合遗传算法的热轧生产调度优化方法

热轧生产调度是一个复杂的约束组合优化问题,其生产约束包括连续轧制板坯的宽度、厚度和硬度跳变要求,轧制单元的最大长度,产品库存及交货期等.基于多旅行商模型,建立了热轧生产批量调度问题的优化模型,并提出一种混合遗传算法(遗传算法、局部搜索)求解该问题.通过应用串行边重组和并行边重组的遗传交叉算子,算法在优化过程中可以很好地处理调度约束.针对工业数据的仿真结果证明该调度模型和混合遗传算法的并行求解策略可以有效地解决热轧生产批量调度问题.     

Two-machine flow shop scheduling integrated with preventive maintenance planning

This paper investigates an integrated optimisation problem of production scheduling and preventive maintenance (PM) in a two-machine flow shop with time to failure of each machine subject to a Weibull probability distribution. The objective is to find the optimal job sequence and the optimal PM decisions before each job such that the expected makespan is minimised. To investigate the value of integrated scheduling solution, computational experiments on small-scale problems with different configurations are conducted with total enumeration method, and the results are compared with those of scheduling without maintenance but with machine degradation, and individual job scheduling combined with independent PM planning. Then, for large-scale problems, four genetic algorithm (GA) based heuristics are proposed. The numerical results with several large problem sizes and different configurations indicate the potential benefits of integrated scheduling solution and the results also show that proposed GA-based heuristics are efficient for the integrated problem.     

Modular design of a hybrid genetic algorithm for a flexible job–shop scheduling problem

The aim of the job–shop scheduling problem is to optimize the task planning in an industrial plant satisfying time and technological constraints. The existing algorithmic and mathematical methods for solving this problem usually have high computational complexities making them intractable. Flexible job–shop scheduling becomes even more complex, since it allows one to assign each operation to a resource from a set of suitable ones. Alternative heuristic methods are only able to satisfy part of the constraints applicable to the problem. Moreover, these solutions usually offer little flexibility to adapt them to new requirements. This paper describes research within heuristic methods that combines genetic algorithms with repair heuristics. Firstly, it uses a genetic algorithm to provide a non-optimal solution for the problem, which does not satisfy all its constraints. Then, it applies repair heuristics to refine this solution. There are different types of heuristics, which correspond to the different types of constraints. A heuristic is intended to evaluate and slightly modify a solution that violates a constraint in a way that avoids or mitigates such violation. This approach improves the adaptability of the solution to a problem, as some changes can be addressed just modifying the considered chromosome or heuristics. The proposed solution has been tested in order to analyse its level of constraint satisfaction and its makespan, which are two of the main parameters considered in these types of problems. The paper discusses this experimentation showing the improvements over existing methods.     

求解混流装配线调度问题的蚁群算法

以最小化总的传送中断时间为目标函数的混流装配线调度问题是丰田生产方式中自动化概念的一个重要问题,而新颖的蚁群算法具有通用性、鲁棒性、并行搜索以及易于与其他启发式算法结合的优点,可以解决多种组合优化问题,对其进行了改进,以便更适于求解混流装配线的调度问题。实验表明：改进的蚁群算法解决了混流装配线的调度问题,得到了优于分支定界法、模拟退火法和遗传算法的可行解。     

A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application

The assembly flowshop scheduling problem has been addressed recently in the literature. There are many problems that can be modeled as assembly flowshop scheduling problems including queries scheduling on distributed database systems and computer manufacturing. The problem has been addressed with respect to either makespan or total completion time criterion in the literature. In this paper, we address the problem with respect to a due date-based performance measure, i.e., maximum lateness. We formulate the problem and obtain a dominance relation. Moreover, we propose three heuristics for the problem: particle swarm optimization (PSO), Tabu search, and EDD. PSO has been used in the areas of function optimization, artificial neural network training, and fuzzy system control in the literature. In this paper, we show how it can be used for scheduling problems. We have conducted extensive computational experiments to compare the three heuristics along with a random solution. The computational analysis indicates that Tabu outperforms the others for the case when the due dates range is relatively wide. It also indicates that the PSO significantly outperforms the others for difficult problems, i.e., tight due dates. Moreover, for difficult problems, the developed dominance relation helps reduce error by 65%.     

基于遗传禁忌算法的多目的间歇过程调度问题求解

由于组合爆炸特性,多目的厂的调度问题很难求解大规模甚至中等规模的问题,本文采用一种新的随机性优化技术一基于禁忌技术的遗传算法点(Tabu-genetic algorithm,TGA)来对该问题进行求解,引入新的选择策略和变异方法．并以零等待的多目的间歇过程调度为实例,计算表明同已有的方法相比,该方法求解效率高、收敛速度快、使用简单方便,可有效的克服计算负荷和求解质量之间的冲突,是一种求解多目的厂间歇过程调度问题的有效算法。     

Two-stage hybrid flowshop scheduling with simultaneous processing machines

Simultaneous processing machines, common in processing industries such as steel and food production, can process several jobs simultaneously in the first-in, first-out manner. However, they are often highly energy-consuming. In this paper, we study a new two-stage hybrid flowshop scheduling problem, with simultaneous processing machines at the first stage and a single no-idle machine with predetermined job sequence at the second stage. A mixed integer programming model is proposed with the objective of minimizing the total processing time to reduce energy consumption and improve production efficiency. We give a sufficient and necessary condition to construct feasible sequencing solutions and present an effective approach to calculate the time variables for a feasible sequencing solution. Based on these results, we design a list scheduling heuristic algorithm and its improvement. Both heuristics can find an optimal solution under certain conditions with complexity O(nlogn), where n is the number of jobs. Our experiments verify the efficiency of these heuristics compared with classical heuristics in the literature and investigate the impacts of problem size and processing times.     

An inherently parallel method for heuristic problem-solving. II.Example applications

For pt.I. see ibid., p.1006-15. This paper presents the application of parallel dynamic interaction (PDI) to three real problem domains: the flowshop scheduling problem, the job-shop scheduling problem and the vertex cover problem. Specific examples are provided as to how the general PDI framework, introduced in part I of this paper, can be applied to a particular problem. The results of an empirical study of 90 example instances of these problems indicate that PDI consistently out-performs previously published heuristics for the vertex cover problem, and can typically generate solutions within a few percent of optimal for flow-shop and job-shop problems. Out of the 76 examples for which the optimal solution could be determined, PDI was able to produce results averaging within 4% of optimal. In over 30% of the cases, PDI was able to find the optimal solution. In no case did the PDI solution deviate more than 15% from optimal. It is also seen that the time taken by PDI to arrive at these solutions is negligible compared to that taken by conventional search techniques. This provides strong empirical evidence that PDI is capable of generating high quality solutions to exponentially and super-exponentially hard problems in reasonably short periods of time     

MIP formulation and heuristics for multi-stage capacitated lot-sizing and scheduling problem with availability constraints

In this paper, the problem of lot-sizing and scheduling of multiple product types in a capacitated flow shop with availability constraints for multi-period planning horizon is considered. In many real production systems, machines may be unavailable due to breakdowns or preventive maintenance activities, thus integrating lot-sizing and scheduling with maintenance planning is necessary to model real manufacturing conditions. Two variants are considered to deal with the maintenance activities. In the first, the starting times of maintenance tasks are fixed, whereas in the second one, maintenance must be carried out in a given time window. A new mixed-integer programming (MIP) model is proposed to formulate the problem with sequence-dependent setups and availability constraints. The objective is to find a production and preventive maintenance schedule that minimizes production, holding and setup costs. Three MIP-based heuristics with rolling horizon framework are developed to generate the integrated plan. Computational experiments are performed on randomly generated instances to show the efficiency of the heuristics. To evaluate the validity of the solution methods, problems with different scales have been studied and the results are compared with the lower bound. Computational experiments demonstrate that the performed methods have good-quality results for the test problems.     

列队竞争算法求解多产品间歇生产过程排序问题

由于组合爆炸特性,多产品厂的排序问题很难求解大规模甚至中等规模的问题,本文采用一种新的随机型进化搜索算法——列队竞争算法来对该问题进行求解,引入新的选择策略和变异方法。计算表明同已有的方法相比,该方法求解效率高、收敛速度快、使用简单方便,是一种求解多产品间歇过程排序问题的有效算法,为多目的厂间歇过程排序研究提供了新思路。     

Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics

We propose a general-purpose heuristic approach combining metaheuristics and mixed integer programming to find high quality solutions to the challenging single- and parallel-machine capacitated lotsizing and scheduling problem with sequence-dependent setup times and costs. Commercial solvers fail to solve even medium-sized instances of this NP-hard problem; therefore, heuristics are required to find competitive solutions. We develop construction, improvement and search heuristics all based on MIP formulations. We then compare the performance of these heuristics with those of two metaheuristics and other MIP-based heuristics that have been proposed in the literature, and to a state-of-the-art commercial solver. A comprehensive set of computational experiments shows the effectiveness and efficiency of the main approach, a stochastic MIP-based local search heuristic, in solving medium to large size problems. Our solution procedures are quite flexible and may easily be adapted to cope with model extensions or to address different optimization problems that arise in practice.