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

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

A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line

In this paper, the problem of determining cyclic schedules for a material handling hoist in the printed-circuit-board(PCB) electroplating line is considered. The objective of this research is to determine an optimal simple-cycle schedule of the hoist which in turn maximizes the line throughput rate. Previous approaches to the cyclic hoist scheduling problem are all mathematical programming-based approaches to develop cyclic schedules(Mixed Integer Programming, Linear Programming based Branch and Bound, Branch and Bound Search Method and so on). In this paper, a genetic algorithm-based approach for a single hoist scheduling in the PCB electroplating line is described. Through an experiment for the well known example data, the proposed algorithm is shown to be more efficient than the previous mathematical programming-based algorithm.     

解不同交货期并行机调度问题的并行遗传算法

为有效地解决不同交货期窗口下的非等同并行多机提前/拖后调度问题,设计了一种分段编码的混合遗传算法。此编码方式能反映工件的分配序列,并利用调度优先级规则和最好适应值规则相结合的启发式算法对其顺序进行了调整,加快了收敛速度。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于遗传算法,有着较高的并行性,并能适用于大规模不同交货期窗口下非等同并行多机提前/拖后调度问题。     

A genetic algorithm approach for the single machine scheduling problem with linear earliness and quadratic tardiness penalties

In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs, and no machine idle time. We propose a genetic approach based on a random key alphabet. Several genetic algorithms based on this approach are presented. These versions differ on the generation of the initial population, as well as on the use of local search. The proposed procedures are compared with existing heuristics, as well as with optimal solutions for the smaller instance sizes.     

A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints

We study a real-world complex hybrid flow-shop scheduling problem arising from a bio-process industry. There are a variety of constraints to be taken into account, in particular zero intermediate capacity and limited waiting time between processing stages. We propose an exact solution approach for this optimization problem, based on a discrete time representation and a mixed-integer linear programming formulation. The proposed solution algorithm makes use of a new family of valid inequalities exploiting the fact that a limited waiting time is imposed on jobs between two successive production stages. The results of our computational experiments confirm that the proposed method produces good feasible schedules for industrial instances.     

The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach

In this paper, we consider the manpower allocation problem with time windows, job-teaming constraints and a limited number of teams (m-MAPTWTC). Given a set of teams and a set of tasks, the problem is to assign to each team a sequential order of tasks to maximize the total number of assigned tasks. Both teams and tasks may be restricted by time windows outside which operation is not possible. Some tasks require cooperation between teams, and all teams cooperating must initiate execution simultaneously. We present an integer programming model for the problem, which is decomposed using Dantzig–Wolfe decomposition. The problem is solved by column generation in a branch-and-price framework. Simultaneous execution of tasks is enforced by the branching scheme. To test the efficiency of the proposed algorithm, 12 realistic test instances are introduced. The algorithm is able to find the optimal solution in 11 of the test instances. The main contribution of this article is the addition of synchronization between teams in an exact optimization context.     

A hybrid algorithm for vehicle routing problem with time windows

Vehicle routing problem with time windows (VRPTW) is a well-known combinatorial problem. Many researches have presented meta-heuristics are effective approaches for VRPTW. This paper proposes a hybrid approach, which consists of ant colony optimization (ACO) and Tabu search, to solve the problem. To improve the performance of ACO, a neighborhood search is introduced. Furthermore, when ACO is close to the convergence Tabu search is used to maintain the diversity of ACO and explore new solutions. Computational experiments are reported for a set of the Solomon’s 56 VRPTW and the approach is compared with some meta-heuristic published in literature. Results show that considering the tradeoff of quality and computation time, the hybrid algorithm is a competitive approach for VRPTW.     

基于改进遗传算法的带时间窗车辆路径问题研究

该文以最小化配送时间为目标,研究带时间窗的车辆路径问题,建立整数规划模型。为了加快遗传算法的收敛速度和寻优能力,提出一种改进遗法算法IGALS(Improved Genetic Algorithm with Local Search)。改进算法借用精英保留策略,采用点交叉和段交叉算子结合的交叉算子;提出路段允许延迟时间概念,并以此为依据使用局部搜索策略进一步提高解的质量。通过Solomon标准算例测试,验证了改进算法(IGALS)较简单遗传算法(GA)具有更好的全局寻优能力和更快的收敛速度。     

Exact algorithms for single-machine scheduling with time windows and precedence constraints

We study a single-machine scheduling problem that is a generalization of a number of problems for which computational procedures have already been published. Each job has a processing time, a release date, a due date, a deadline, and a weight representing the penalty per unit-time delay beyond the due date. The goal is to schedule all jobs such that the total weighted tardiness penalty is minimized and both the precedence constraints as well as the time windows (implied by the release dates and the deadlines) are respected. We develop a branch-and-bound algorithm that solves the problem to optimality. Computational results show that our approach is effective in solving medium-sized instances, and that it compares favorably with existing methods for special cases of the problem.     

A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times

This paper presents a hybrid approach based on the integration between a genetic algorithm (GA) and concepts from constraint programming, multi-objective evolutionary algorithms and ant colony optimization for solving a scheduling problem. The main contributions are the integration of these concepts in a GA crossover operator. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid approach is carried out to compare the performance of the GA and the hybrid genetic algorithm (HGA) approaches on different benchmarks from the literature. The numerical experiments demonstrate the HGA efficiency and effectiveness which generates solutions that approach those of the known reference sets and improves several lower bounds.     

A hybrid algorithm for the cyclic hoist scheduling problem with two transportation resources

In automated electroplating lines, computer-controlled hoists are used to transfer parts from a processing resource to another one. Products are mounted into carriers and immersed sequentially in a series of tanks following a given sequence.     

A genetic algorithm for JIT single machine scheduling with preemption and machine idle time

This paper concerns with the concept of preemption in just-in-time single machine scheduling problem, with allowable machine idle time. We proposed a new model, with non-linear terms and integer variables which cannot be solved efficiently for large size problems due to its NP-hardness. To solve the model for real size applications, genetic algorithm is applied. These genetic procedures are also quite close to the optimum and provided an optimal solution for most of the test problems. Numerical examples show that the proposed algorithm is efficient and effective.     

A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and complex combinatorial problem, which has received considerable attention in recent years. This problem has been addressed using many different techniques including both exact and heuristic methods. The VRPTW benchmark problems of Solomon [Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 1987; 35(2): 254–65] have been most commonly chosen to evaluate and compare all algorithms. Results from exact methods have been improved considerably because of parallel implementations and modern branch-and-cut techniques. However, 24 out of the 56 high order instances from Solomon's original test set still remain unsolved. Additionally, in many cases a prohibitive time is needed to find the exact solution. Many of the heuristic methods developed have proved to be efficient in identifying good solutions in reasonable amounts of time. Unfortunately, whilst the research efforts based on exact methods have been focused on the total travel distance, the focus of almost all heuristic attempts has been on the number of vehicles. Consequently, it is more difficult to compare and take advantage of the strong points from each approach. This paper proposes a robust heuristic approach for the VRPTW using travel distance as the main objective through an efficient genetic algorithm and a set partitioning formulation. The tests were produced using real numbers and truncated data type, allowing a direct comparison of its results against previously published heuristic and exact methods. Furthermore, computational results show that the proposed heuristic approach outperforms all previously known and published heuristic methods in terms of the minimal travel distance.     

A tabu search approach to the truck scheduling problem with multiple docks and time windows

While organizing the cross-docking operations, cross-dock managers are confronted with many decision problems. One of these problems is the truck scheduling problem. This paper presents a truck scheduling problem that is concerned with both inbound and outbound trucks at multiple dock doors. The objective is to minimize the total travel time and the total tardiness. The truck scheduling problem under study is described in detail and a mathematical model of the problem is provided which can be solved to optimality with a mixed integer programming solver, at the expense of a high computation time. Next, a tabu search approach is presented. Experimental results on new benchmark instances indicate that the proposed tabu search is able to find good quality results in a short time period, thus offering potential for integration in cross-docking decision support systems.     

Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm

The present study investigates the cost concerns of distribution centers and formulates a vehicle routing problem with time window constraints accordingly. Based on the embedded structure of the original problem, a decomposition technique is employed to decompose the original problems to a clustering problem (main problem) and a set of traveling salesman problems (sub-problems) with time window constraints. This decomposition not only reduces the problem size but also enable the use of simpler solution procedures. A genetic algorithm is developed to solve the clustering problem, while a simple heuristic algorithm is formulated to solve the set of traveling salesman problems. The solution of the original problem is obtained through iterative interactions between the main problem and the set of sub-problems. The performance of the proposed approach is compared with the well-known insertion method and a manual scheduling of a distribution center.     

Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm

This paper presents a new model and solution for multi-objective vehicle routing problem with time windows (VRPTW) using goal programming and genetic algorithm that in which decision maker specifies optimistic aspiration levels to the objectives and deviations from those aspirations are minimized. VRPTW involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. This paper uses a direct interpretation of the VRPTW as a multi-objective problem where both the total required fleet size and total traveling distance are minimized while capacity and time windows constraints are secured. The present work aims at using a goal programming approach for the formulation of the problem and an adapted efficient genetic algorithm to solve it. In the genetic algorithm various heuristics incorporate local exploitation in the evolutionary search and the concept of Pareto optimality for the multi-objective optimization. Moreover part of initial population is initialized randomly and part is initialized using Push Forward Insertion Heuristic and λ-interchange mechanism. The algorithm is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances. Results show that the suggested approach is quiet effective, as it provides solutions that are competitive with the best known in the literature.     

A hybrid genetic algorithm for multi-depot homogenous locomotive assignment with time windows

This paper presents a hybrid genetic algorithm to solve a multi-depot homogenous locomotive assignment problem with time windows. The locomotive assignment problem is to assign a set of homogeneous locomotives locating in a set of dispersed depots to a set of pre-schedules trains that are supposed to be serviced in pre-specified hard/soft time windows. A mathematical model is presented, using vehicle routing problem with time windows (VRPTW) for formulation of the problem. A cluster-first, route-second approach is used to inform the multi-depot locomotive assignment to a set of single depot problems and after that we solve each problem independently. Each single depot problem is solved heuristically by a hybrid genetic algorithm that in which Push Forward Insertion Heuristic (PFIH) is used to determine the initial solution and λ-interchange mechanism is used for neighborhood search and improving method. A medium sized numerical example with different scenarios is presented and examined to more clarification of the approach as well as to check capabilities of the model and algorithm. Also some of the results are compared with the solutions produced by branch & bound technique to determine validity and quality of the model. The experiments with a set of 15 completely random generated instance problems indicate that this algorithm is efficient and solves the problem in a polynomial time.     

Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor

The problem presented in this paper is a generalization of the usual coupled-tasks scheduling problem in presence of compatibility constraints. The reason behind this study is the data acquisition problem for a submarine torpedo. We investigate a particular configuration for coupled tasks (any task is divided into two sub-tasks separated by an idle time), in which the idle time of a coupled task is equal to the sum of durations of its two sub-tasks. We prove \(\mathcal{NP}\)-completeness of the minimization of the schedule length, we show that finding a solution to our problem amounts to solving a graph problem, which in itself is close to the minimum-disjoint-path cover (min-DCP) problem. We design a \((\frac{3a+2b}{2a+2b})\)-approximation, where a and b (the processing time of the two sub-tasks) are two input data such as a>b>0, and that leads to a ratio between \(\frac {3}{2}\) and \(\frac{5}{4}\). Using a polynomial-time algorithm developed for some class of graph of min-DCP, we show that the ratio decreases to \(\frac{1+\sqrt{3}}{2}\approx 1.37\).     

A robust approach for the single machine scheduling problem

This paper describes a robust approach for the single machine scheduling problem 1|r _i |L _max. The method is said to be robust since it characterizes a large set of optimal solutions allowing to switch from one solution to another, without any performance loss, in order to face potential disruptions which occur during the schedule execution. It is based on a dominance theorem that characterizes a set of dominant sequences, using the interval structure defined by the relative order of the release and the due dates of jobs. The performance of a set of dominant sequences can be determined in polynomial time by computing the most favorable and the most unfavorable sequences associated with each job, with regard to the lateness criterion. A branch and bound procedure is proposed which modifies the interval structure of the problem in order to tighten the dominant set of sequences so that only the optimal sequences are conserved.     

A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) provides an excellent algorithmic framework for solving multi-objective optimization problems. It decomposes a target problem into a set of scalar sub-problems and optimizes them simultaneously. Due to its simplicity and outstanding performance, MOEA/D has been widely studied and applied. However, for solving the multi-objective vehicle routing problem with time windows (MO-VRPTW), MOEA/D faces a difficulty that many sub-problems have duplicated best solutions. It is well-known that MO-VRPTW is a challenging problem and has very few Pareto optimal solutions. To address this problem, a novel selection operator is designed in this work to enhance the original MOEA/D for dealing with MO-VRPTW. Moreover, three local search methods are introduced into the enhanced algorithm. Experimental results indicate that the proposed algorithm can obtain highly competitive results on Solomon׳s benchmark problems. Especially for instances with long time windows, the proposed algorithm can obtain more diverse set of non-dominated solutions than the other algorithms. The effectiveness of the proposed selection operator is also demonstrated by further analysis.