成组加工中有主从调整时间的最大延迟问题

针对钢管生产过程具有多产品和主从调整时间特性的实际批组调度问题,以最小化工件的最大延迟为目标函数,建立了问题的0-1混合整数规划模型;进而分析了问题的优化特性,提出了基于优化特性的禁忌搜索算法.仿真结果表明该算法是可行而有效的.     

A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals

In this paper, we consider a single batch machine scheduling problem with incompatible job families and dynamic job arrivals. The objective is to minimize the total completion time. This problem is known to be strongly NP-hard. We present several dominance properties and two types of lower bounds, which are incorporated to construct a basic branch and bound algorithm. Furthermore, according to the characteristics of dynamic job arrivals, a decomposed branch and bound algorithm is proposed to improve the efficiency. The proposed algorithms are tested on a large set of randomly generated problem instances.     

A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine

This paper deals with the single machine scheduling problem to minimize the total weighted tardiness in the presence of sequence dependent setup. Firstly, a mathematical model is given to describe the problem formally. Since the problem is NP-hard, a general variable neighborhood search (GVNS) heuristic is proposed to solve it. Initial solution for the GVNS algorithm is obtained by using a constructive heuristic that is widely used in the literature for the problem. The proposed algorithm is tested on 120 benchmark instances. The results show that 37 out of 120 best known solutions in the literature are improved while 64 instances are solved equally. Next, the GVNS algorithm is applied to single machine scheduling problem with sequence dependent setup times to minimize the total tardiness problem without changing any implementation issues and the parameters of the GVNS algorithm. For this problem, 64 test instances are solved varying from small to large sizes. Among these 64 instances, 35 instances are solved to the optimality, 16 instances' best-known results are improved, and 6 instances are solved equally compared to the best-known results. Hence, it can be concluded that the GVNS algorithm is an effective, efficient and a robust algorithm for minimizing tardiness on a single machine in the presence of setup times.     

A novel two-phase heuristic method for vehicle routing problem with backhauls

This paper raises a novel two-phase heuristic method to solve vehicle routing problems with backhauls. Differing from other vehicle routing problems, we consider the travel speed of vehicle to be time dependent, which will be used for the model of rush hour in an urban city. In the first phase, the original solution is generated by extending traditional heuristic methods and in the second phase, the reactive tabu search algorithm is used to optimize the original solution. We verified that this algorithm is efficient in a number of standard test cases. After comparison with the closest neighboring search algorithm, we found that the results of two-phase heuristic methods are more reasonable.     

Minimizing Total Weighted Tardiness in a Generalized Job Shop

We consider a generalization of the classical job shop scheduling problem with release times, positive end–start time lags, and a general precedence graph. As objective we consider the total weighted tardiness. We use a tabu search algorithm to search for the order in which the operations are processed on each machine. Given a sequence of operations on each machine, we determine optimal starting times by solving a maximum cost flow problem. This solution is used to determine the neighborhood for our tabu search algorithm. All sequences in our neighborhood are obtained by swapping certain pairs of adjacent operations. We show that only swaps that possess a certain property can improve the current solution; if no such swap is available in the neighborhood, then the current solution is globally optimal. In the computational results we compare our method with other procedures proposed in literature. Our tabu search algorithm seems to be effective both with respect to time and solution quality. The research was carried out at the Technische Universiteit Eindhoven and the Universiteit Utrecht with support of Baan and the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT).     

An Advanced Tabu Search Algorithm for the Job Shop Problem

The job shop scheduling problem with the makespan criterion is a certain NP-hard case from OR theory having excellent practical applications. This problem, having been examined for years, is also regarded as an indicator of the quality of advanced scheduling algorithms. In this paper we provide a new approximate algorithm that is based on the big valley phenomenon, and uses some elements of so-called path relinking technique as well as new theoretical properties of neighbourhoods. The proposed algorithm owns, unprecedented up to now, accuracy, obtainable in a quick time on a PC, which has been confirmed after wide computer tests.     

Algorithms for a realistic variant of flowshop scheduling

This paper deals with a realistic variant of flowshop scheduling, namely the hybrid flexible flowshop. A hybrid flowshop mixes the characteristics of regular flowshops and parallel machine problems by considering stages with parallel machines instead of having one single machine per stage. We also investigate the flexible version where stage skipping might occur, i.e., not all stages must be visited by all jobs. Lastly, we also consider job sequence dependent setup times per stage. The optimization criterion considered is makespan minimization. While many approaches for hybrid flowshops have been proposed, hybrid flexible flowshops have been rarely studied. The situation is even worse with the addition of sequence dependent setups. In this study, we propose two advanced algorithms that specifically deal with the flexible and setup characteristics of this problem. The first algorithm is a dynamic dispatching rule heuristic, and the second is an iterated local search metaheuristic. The proposed algorithms are evaluated by comparison against seven other high performing existing algorithms. The statistically sound results support the idea that the proposed algorithms are very competitive for the studied problem.     

The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan

In this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n(n/m+1)^m) time dynamic programming algorithm and an O(mk^k+1P^2k−1) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the processing times of all families. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme for the problem.     

Local Search Genetic Algorithms for the Job Shop Scheduling Problem

In previous work, we developed three deadlock removal strategies for the job shop scheduling problem (JSSP) and proposed a hybridized genetic algorithm for it. While the genetic algorithm (GA) gave promising results, its performance depended greatly on the choice of deadlock removal strategies employed. This paper introduces a genetic algorithm based scheduling scheme that is deadlock free. This is achieved through the choice of chromosome representation and genetic operators. We propose an efficient solution representation for the JSSP in which the job task ordering constraints are easily encoded. Furthermore, a problem specific crossover operator that ensures solutions generated through genetic evolution are all feasible is also proposed. Hence, both checking of the constraints and repair mechanism can be avoided, thus resulting in increased efficiency. A mutation-like operator geared towards local search is also proposed which further improves the solution quality. Lastly, a hybrid strategy using the genetic algorithm reinforced with a tabu search is developed. An empirical study is carried out to test the proposed strategies.     

Improvement of constructive heuristics using variable neighbourhood descent for scheduling a flow shop with sequence dependent setup time

This paper deals with the problem of scheduling a flow shop operating in a sequence dependent setup time environment. The objective is to determine the sequence that minimises the makespan. Two efficient neighbourhood search-based heuristics have been developed and tested using 960 problems, and the results obtained reveal their usefulness. The algorithms make use of two existing constructive heuristics. A neighbourhood search known as variable neighbourhood descent is used to improve the two constructive heuristics. Experimentation is carried out on the 96 groups of problems with 10 problem instances in each group. Performance analysis is carried out using the relative performance improvement of each heuristic. The analysis shows a consistently better performance of the neighbourhood-based improvement heuristics. A paired comparison test is used for validating the superiority of the proposed heuristics. The statistical analysis reveals that the performance of the neighbourhood-based heuristics is very much dependent on the initial constructive heuristics used.     

基于遗传和禁忌搜索算法求解车间调度优化问题

针对柔性生产环境下的车间调度问题,在考虑遗传算法早熟收敛问题和禁忌搜索法自适应优点的基础上,将遗传算法和禁忌搜索法结合起来,提出了基于遗传和禁忌搜索的混合动态优化调度算法,并用实例对该算法进行了仿真研究。结果表明,此算法有很好收敛精度,是可行的,并且能够在扰动发生后提供新的调度计划,与传统的调度算法相比较,体现了明显的优越性。     

求解无等待流水调度的基于禁忌搜索的混合算法

本文提出了解决最小完工时间的无等待流水调度问题的基于禁忌搜索的混合算法。算法结合了调度规则和禁忌搜索算法的优点,首先利用调度规则构造较好的初始解,既可以加快禁忌搜索算法的收敛速度,也可以降低整个算法的运算量,使算法有更好的工程实用性;然后使用变邻域结构的禁忌搜索算法改进当前解。在保持可达性的基础上,该算法缩小了邻域规模和减少了计算时间。数值仿真实验表明,该算法是有效的。     

A tabu search algorithm for order acceptance and scheduling

We consider a make-to-order production system, where limited production capacity and order delivery requirements necessitate selective acceptance of the orders. Since tardiness penalties cause loss of revenue, scheduling and order acceptance decisions must be taken jointly to maximize total revenue. We present a tabu search algorithm that solves the order acceptance and scheduling problem on a single machine with release dates and sequence dependent setup times. We analyze the performance of the tabu search algorithm on an extensive set of test instances with up to 100 orders and compare it with two heuristics from the literature. In the comparison, we report optimality gaps which are calculated with respect to bounds generated from a mixed integer programming formulation. The results show that the tabu search algorithm gives near optimal solutions that are significantly better compared to the solutions given by the two heuristics. Furthermore, the run time of the tabu search algorithm is very small, even for 100 orders. The success of the proposed heuristic largely depends on its capability to incorporate in its search acceptance and scheduling decisions simultaneously.     

Tardiness minimization in a flexible job shop: A tabu search approach

This paper addresses the problem of scheduling jobs in a flexible job shop with the objective of minimizing total tardiness. The flexible job shop differs from the classical job shop in that each of the operations associated with a job can be processed on any of a set of alternative machines. Two heuristics based on tabu search are developed for this problem: a hierarchical procedure and a multiple start procedure. The procedures use dispatching rules to obtain an initial solution and then search for improved solutions in neighborhoods generated by the critical paths of the jobs in a disjunctive graph representation. Diversification strategies are also implemented and tested. The outcomes of extensive computational results are reported.     

一种求解车间作业调度的自适应混合遗传算法

针对遗传算法和禁忌搜索算法在求解车间作业调度问题存在的全局收敛性差、种群早熟化、收敛速度慢等缺陷,提出了一种自适应遗传禁忌搜索算法。算法通过自适应调整遗传算子中的变异概率,改善了遗传算法的收敛速度;通过增加禁忌表来选择杂交产生的个体,避免迂回搜索,以禁忌搜索算法作为变异算子,增加种群的多样性,避免算法陷入局部最优。通过仿真实例,验证了算法的收敛性和抗局部收敛性。     

硬时间窗VRP的混合变邻域禁忌搜索算法

为了寻求带硬时间窗的车辆路径优化问题的高质量近似解;针对现有数学模型对时间窗约束考虑不充分;建立了最小化车辆数和总行驶距离的双目标非线性优化模型;提出了一种混合变邻域禁忌搜索求解算法。一方面;采用改进的节约算法生成初始解;设计了3种删除算子和一种插入算子对初始解进行扰动优化;为后续禁忌搜索提供优良的初始解;另一方面;基于4种邻域构造算子进行禁忌迭代搜索;利用禁忌搜索的灵活存储结构、避免迂回搜索的禁忌准则和增强多样性搜索的特赦准则有效摆脱局部最优解;最终实现全局优化。在56个Solomon和18个Homberger基准算例上的实验结果表明;该算法的求解质量优于文献中两种同类型搜索算法;具有良好的收敛性和稳定性;且在42个基准实例上获得了比当前已知最好解更低的车辆总行驶距离。     

Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method

An adaptive memory projection (referred as AMP) method is developed for multidimensional knapsack problems (referred as the MKP) with generalized upper bound constraints. All the variables are divided into several generalized upper bound (referred as GUB) sets and at most one variable can be chosen from each of the GUB sets. The MKP with GUBs (referred as the GUBMKP) can be applied to many real-world problems, such as capital budgeting, resource allocation, cargo loading, and project selection. Due to the complexity of the GUBMKP, good metaheuristics are sought to tackle this problem.The AMP method keeps track of components of good solutions during the search and creates provisional solution by combining components of better solutions. The projection method, which can free the selected variables while fixing the others, is very useful for metaheuristics, especially when tackling large-scale combinatorial optimization. In this paper, the AMP method is implemented by iteratively using critical event tabu search as a search routine, and CPLEX in the referent optimization stage. Variables that are strongly determined, consistent, or attractive, are identified in the search process. Selected variables from this pool are fed into CPLEX as a small subproblem. In addition to the diversification effect within critical event tabu search, the pseudo-cut inequalities and an adjusted frequency penalty scalar are also applied to increase opportunities of exploring new regions.This study conducts a comprehensive sensitivity analysis on the parameters and strategies used in the proposed AMP method. The computational results show several variants of the AMP method outperforms the tight oscillation method in the literature of GUBMKP. On average, consistent variables tend to perform best as a pure strategy. A pure strategy equipped with local search can lead into even better results. Last but not least, testing different types of variables in the referent optimization stage before selecting just one of the pure strategies is found to be very helpful.