Scheduling trains as a blocking parallel-machine job shop scheduling problem

In this paper, the train scheduling problem is modelled as a blocking parallel-machine job shop scheduling (BPMJSS) problem. In the model, trains, single-track sections and multiple-track sections, respectively, are synonymous with jobs, single machines and parallel machines, and an operation is regarded as the movement/traversal of a train across a section. Due to the lack of buffer space, the real-life case should consider blocking or hold-while-wait constraints, which means that a track section cannot release and must hold the train until next section on the routing becomes available. Based on literature review and our analysis, it is very hard to find a feasible complete schedule directly for BPMJSS problems. Firstly, a parallel-machine job-shop-scheduling (PMJSS) problem is solved by an improved shifting bottleneck procedure (SBP) algorithm without considering blocking conditions. Inspired by the proposed SBP algorithm, feasibility satisfaction procedure (FSP) algorithm is developed to solve and analyse the BPMJSS problem, by an alternative graph model that is an extension of the classical disjunctive graph models. The proposed algorithms have been implemented and validated using real-world data from Queensland Rail. Sensitivity analysis has been applied by considering train length, upgrading track sections, increasing train speed and changing bottleneck sections. The outcomes show that the proposed methodology would be a very useful tool for the real-life train scheduling problems.     

An efficient Lagrangean heuristic for rental vehicle scheduling

In this article we present a heuristic based on Lagrangean relaxation for scheduling rental vehicles. The scheduling problem can be formulated as a set of large assignment problems with linking constraints. We discuss the theory behind the heuristic, including the ability to obtain lower bounds. The heuristic is based on ideas first introduced by D. Wedelin.     

Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach

This work proposes a hybrid metaheuristic (HMH) approach which integrates several features from tabu search (TS), simulated annealing (SA) and variable neighbourhood search (VNS) in a new configurable scheduling algorithm. In particular, either a deterministic or a random candidate list strategy can be used to generate the neighbourhood of a solution, both a tabu list mechanism and the SA probabilistic rule can be adopted to accept solutions, and the dimension of the explored neighbourhood can be dynamically modified. The considered class of scheduling problems is characterized by a set of independent jobs to be executed on a set of parallel machines with non-zero ready times and sequence dependent setups. In particular, the NP-hard generalized parallel machine total tardiness problem (GPMTP) recently defined by Bilge et al. [A tabu search algorithm for parallel machine total tardiness problem. Computers & Operations Research 2004;31:397–414], is faced. Several alternative configurations of the HMH have been tested on the same benchmark set used by Bilge et al. The results obtained highlight the appropriateness of the proposed approach.     

Search heuristics for a parallel machine scheduling problem with ready times and due dates

We consider a problem of scheduling orders on identical parallel machines. An order can be released after a given ready time and must be completed before its due date. An order is split into multiple jobs (batches) and a job is processed on one of the parallel machines. The objective of the scheduling problem is to minimize the holding costs of orders including work-in-process as well as finished job inventories. We suggest two local search heuristics, simulated annealing and taboo search algorithms, for the problem. Performance of the suggested algorithms is tested through computational experiments on randomly generated test problems.     

一种新的混合生产调度问题的优化求解

研究了一种新的生产调度问题的优化问题,针对这种新的调度模式,设计了一种两层遗传算法进行优化求解。算法采用了上下两层共同进化,上层遗传算法优化产品生产过程中每类产品对应每台设备所生产的物料类型的分配,下层遗传退火算法优化了所有产品子批量的一个排序。在算法的求解过程中,引入了针对该问题的一个新的批量加工时间计算方法来求得最大完成时间指标的值。最后通过系统仿真论证了算法以及批量完工时间计算的有效性。     

Design and analysis of stochastic local search for the multiobjective traveling salesman problem

Stochastic local search (SLS) algorithms are typically composed of a number of different components, each of which should contribute significantly to the final algorithm's performance. If the goal is to design and engineer effective SLS algorithms, the algorithm developer requires some insight into the importance and the behavior of possible algorithmic components. In this paper, we analyze algorithmic components of SLS algorithms for the multiobjective travelling salesman problem. The analysis is done using a careful experimental design for a generic class of SLS algorithms for multiobjective combinatorial optimization. Based on the insights gained, we engineer SLS algorithms for this problem. Experimental results show that these SLS algorithms, despite their conceptual simplicity, outperform a well-known memetic algorithm for a range of benchmark instances with two and three objectives.     

一种求解Job-Shop调度问题的新型蚁群算法

Job-Shop调度问题是一类具有很高理论研究和工程应用价值的问题。针对使用蚁群算法求解Job-Shop调度问题时较难设置合适参数的问题,提出一种动态设置参数的新型蚁群求解算法。分析了蚁群算法中参数对求解结果的影响,给出了算法求解Job-Shop调度问题的关键技术和实现过程。最后对五个基本测试问题进行了仿真实验,并与遗传算法、模拟退火算法、基本蚁群算法进行了比较。结果表明,该算法能得到较优的结果,具有一定的应用价值。     

Ant based Pareto optimal solution for QoS aware energy efficient multicast in wireless networks

Most of the group communication technologies support real-time multimedia applications such as video conferencing and distributed gaming. These applications require quality-of-service (QoS) aware multicast routing protocol to deliver the same data stream to a predefined group of receivers. Since nodes in wireless networks are severely energy constrained due to finite battery source, hence it is of paramount importance that QoS aware multicast routing protocol be energy efficient. Transmission power control is one of the methods used to save energy. In this method, the nodes dynamically adjust the transmission power so that energy consumption in the tree is minimized. However, reduction in the transmission power increases the number of forwarding nodes in the multicast tree. This negatively impacts the QoS in terms of propagation delay, delay jitter, and packet loss etc. In wireless networks, there is a trade-off between the energy consumption and the QoS guarantees provided by the network. We unify these requirements into a multiobjective framework referred to as Energy Efficient QoS Multicast Routing (E²QoSMR). The goal is to simultaneously optimize the total power consumption and the QoS parameters in the multicast tree. We extend two algorithms based on metaphor of swarm intelligence for finding an energy efficient multicast tree satisfying the QoS guarantees. Extensive simulations have been conducted to validate the correctness and efficiency of the algorithms. The simulation result of the algorithms is compared with the nondominated sorting genetic algorithm, NSGA-III. The experimental results are consolidated by statistical analyses that demonstrate the ability of the algorithms to generate the Pareto optimal solution set.     

萤火虫群优化算法在越库调度问题中的应用

萤火虫群优化算法是一种新兴的群体智能优化算法,目前在组合优化领域中的应用比较少。提出萤火虫群优化算法（Glowworm Swarm Optimization,GSO）求解越库调度问题的优化方法。越库调度问题是一类极为复杂的NP难题,是影响越库配送效率的关键问题。依据算法和问题特点,设计基于随机键的两段式最大顺序值编码方法。为了解决GSO算法优化精度低、收敛速度慢等问题,提出逐维移动,贪婪接受的搜索策略。基于社会心理学原理,对位置更新公式进行改进。通过实验仿真,结果表明改进的GSO算法是求解越库调度问题的有效方法。     

Hybrid discrete differential evolution algorithm for biobjective cyclic hoist scheduling with reentrance

Cyclic hoist scheduling problems in automated electroplating lines and surface processing shops attract many attentions and interests both from practitioners and researchers. In such systems, parts are transported from a workstation to another by a material handling hoist. The existing literature mainly addressed how to find an optimal cyclic schedule to minimize the cycle time that measures the productivity of the lines. The material handling cost is an important factor that needs to be considered in practice but seldom addressed in the literature. This study focuses on a biobjective cyclic hoist scheduling problem to minimize the cycle time and the material handling cost simultaneously. We consider the reentrant workstations that are usually encountered in real-life lines but inevitably make the part-flow more complicated. The problem is formulated as a biobjective linear programming model with a given hoist move sequence and transformed into finding a set of Pareto optimal hoist move sequences with respect to the bicriteria. To obtain the Pareto optimal or near-optimal front, a hybrid discrete differential evolution (DDE) algorithm is proposed. In this hybrid evolutional algorithm, the population is divided into several subpopulations according to the maximal work-in-process (WIP) level of the system and the sizes of subpopulations are dynamically adjusted to balance the exploration and exploitation of the search. We propose a constructive heuristic to generate initial subpopulations with different WIP levels, hybrid mutation and crossover operators, an evaluation method that can tackle infeasible individuals and a one-to-one greedy tabu selection method. Computational results on both benchmark instances and randomly generated instances show that our proposed hybrid DDE algorithm outperforms the basic DDE algorithm and can solve larger-size instances than the existing ε-constraint method.     

混合粒子群算法求解多目标柔性作业车间调度问题

柔性作业车间调度问题是生产管理领域和组合优化领域的重要分支.本文提出一种基于Pareto支配的混合粒子群优化算法求解多目标柔性作业车间调度问题.首先采用基于工序排序和机器分配的粒子表达方式,并直接在离散域进行位置更新.其次,提出基于BaldWinian学习策略和模拟退火技术相结合的多目标局部搜索策略,以平衡算法的全局探索能力和局部开发能力.然后引入Pareto支配的概念来比较粒子的优劣性,并采用外部档案保存进化过程中的非支配解.最后用于求解该类问题的经典算例,并与已有算法进行比较,所提算法在收敛性和分布均匀性方面均具有明显优势.     

Target-matching test problem for multiobjective topology optimization using genetic algorithms

This paper describes the multiobjective topology optimization of continuum structures solved as a discrete optimization problem using a multiobjective genetic algorithm (GA) with proficient constraint handling. Crucial to the effectiveness of the methodology is the use of a morphological geometry representation that defines valid structural geometries that are inherently free from checkerboard patterns, disconnected segments, or poor connectivity. A graph- theoretic chromosome encoding, together with compatible reproduction operators, helps facilitate the transmission of topological/shape characteristics across generations in the evolutionary process. A multicriterion target-matching problem developed here is a novel test problem, where a predefined target geometry is the known optimum solution, and the good results obtained in solving this problem provide a convincing demonstration and a quantitative measure of how close to the true optimum the solutions achieved by GA methods can be. The methodology is then used to successfully design a path-generating compliant mechanism by solving a multicriterion structural topology optimization problem.     

复杂反应约束的流程优化调度问题及求解

由于化工流程的生产过程涉及复杂的化学反应,因此,在研究化工流程中的调度问题的时候需要考虑其化学反应所带来的影响因素;这就使得调度的数学模型的建立变得非常的困难。本文针对中小型合成氨流程中的调度问题进行研究,分析合成氨反应的温度、压力、环境等影响因素建立调度的数学模型,采用基于微粒群算法的多目标优化方法对该流程进行优化调度,其结果表明所建的模型具有很好的收敛性和稳定性。     

A new particle swarm optimization for the open shop scheduling problem

This paper presents a new particle swarm optimization (PSO) for the open shop scheduling problem. Compared with the original PSO, we modified the particle position representation using priorities, and the particle movement using an insert operator. We also implemented a modified parameterized active schedule generation algorithm (mP-ASG) to decode a particle position into a schedule. In mP-ASG, we can reduce or increase the search area between non-delay schedules and active schedules by controlling the maximum delay time allowed. Furthermore, we hybridized our PSO with beam search. The computational results show that our PSO found many new best solutions of the unsolved problems.     

拟牛顿粒子群优化算法求解调度问题

针对资源受限的项目调度问题,将粒子群优化算法与拟牛顿优化算法相结合,提出了一种混合粒子群算法。本算法利用粒子群算法求得优化解,然后利用拟牛顿方法对所得到的解进行局部优化,以尽量达到或接近全局最优点。结果表明,本算法能够有效地求解大规模项目调度问题,具有较好的应用价值。     

A parallel double-level multiobjective evolutionary algorithm for robust optimization

Robust optimization is a popular method to tackle uncertain optimization problems. However, traditional robust optimization can only find a single solution in one run which is not flexible enough for decision-makers to select a satisfying solution according to their preferences. Besides, traditional robust optimization often takes a large number of Monte Carlo simulations to get a numeric solution, which is quite time-consuming. To address these problems, this paper proposes a parallel double-level multiobjective evolutionary algorithm (PDL-MOEA). In PDL-MOEA, a single-objective uncertain optimization problem is translated into a bi-objective one by conserving the expectation and the variance as two objectives, so that the algorithm can provide decision-makers with a group of solutions with different stabilities. Further, a parallel evolutionary mechanism based on message passing interface (MPI) is proposed to parallel the algorithm. The parallel mechanism adopts a double-level design, i.e., global level and sub-problem level. The global level acts as a master, which maintains the global population information. At the sub-problem level, the optimization problem is decomposed into a set of sub-problems which can be solved in parallel, thus reducing the computation time. Experimental results show that PDL-MOEA generally outperforms several state-of-the-art serial/parallel MOEAs in terms of accuracy, efficiency, and scalability.     

改进蝙蝠算法柔性作业车间调度问题研究

针对柔性作业车间调度问题,提出了一种改进的离散蝙蝠算法。该算法采用双层编码序列方式,利用均衡机器负载分配策略和插入式解码方案初始化种群,同时设计了离散蝙蝠算法的速度、位置更新的相关算子和操作,引入了平衡调整因子改善算法搜索能力。通过案例测试并与其他算法比较,验证了改进的离散蝙蝠算法可以有效地求解柔性作业车间调度问题,并具有较高的精确度。     

Approximation results for a bicriteria job scheduling problem on a single machine without preemption

We study the problem of minimizing the average weighted completion time on a single machine under the additional constraint that the sum of completion times does not exceed a given bound B(1|∑Cj?B|∑wjCj) for which we propose a (2,1)-approximation algorithm. We also address the problem 1|∑cjCj?B|∑wjCj for which we present a (2,2)-approximation algorithm. After showing that the problem of minimizing two different sums of weighted completion times is intractable, we present an algorithm which computes a (2(1+?),1) (respectively (2(1+?),2))-approximate Pareto curve for the problem 1‖(∑Cj,∑wjCj) (respectively 1‖(∑cjCj,∑wjCj)).     

Recurrent neural network approach for cyclic job shop scheduling problem

While cyclic scheduling is involved in numerous real-world applications, solving the derived problem is still of exponential complexity. This paper focuses specifically on modelling the manufacturing application as a cyclic job shop problem and we have developed an efficient neural network approach to minimise the cycle time of a schedule. Our approach introduces an interesting model for a manufacturing production, and it is also very efficient, adaptive and flexible enough to work with other techniques. Experimental results validated the approach and confirmed our hypotheses about the system model and the efficiency of neural networks for such a class of problems.