Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem

We consider the problem of scheduling a number of jobs on a number of unrelated parallel machines in order to minimize the makespan. We develop three heuristic approaches, i.e., a genetic algorithm, a tabu search algorithm and a hybridization of these heuristics with a truncated branch-and-bound procedure. This hybridization is made in order to accelerate the search process to near-optimal solutions. The branch-and-bound procedure will check whether the solutions obtained by the meta-heuristics can be scheduled within a tight upper bound. We compare the performances of these heuristics on a standard dataset available in the literature. Moreover, the influence of the different heuristic parameters is examined as well. The computational experiments reveal that the hybrid heuristics are able to compete with the best known results from the literature.     

Order acceptance and scheduling to maximize total net revenue in permutation flowshops with weighted tardiness

The order acceptance and scheduling (OAS) problem is important in make-to-order production systems in which production capacity is limited and order delivery requirements are applied. This study proposes a multi-initiator simulated annealing (MSA) algorithm to maximize the total net revenue for the permutation flowshop scheduling problem with order acceptance and weighted tardiness. To evaluate the performance of the proposed MSA algorithm, computational experiments are performed and compared for a benchmark problem set of test instances with up to 500 orders. Experimental results reveal that the proposed heuristic outperforms the state-of-the-art algorithm and obtains the best solutions in 140 out of 160 benchmark instances.     

基于改进迭代贪婪算法的预制构件调度研究

迭代贪婪算法是一种具有较强局部搜索能力的元启发式算法,但由于传统迭代贪婪算法搜索范围过大,搜索效率有限,为了进一步提升传统迭代贪婪算法的搜索能力,考虑到阈值接受算法具有能缩小搜索范围的特点,提出了一种改进的迭代贪婪算法解决流水车间预制生产的订单接受与调度问题。该改进算法是在破坏原调度序列后加入一种基于构造启发式规则的重建策略,并结合阈值接受算法的自适应接受准则用以跳出局部最优。经大量仿真实验结果显示,与传统迭代贪婪算法、禁忌搜索算法以及遗传算法对比,改进的迭代贪婪算法具有更好的求解质量和鲁棒性。     

New approximate algorithms for the customer order scheduling problem with total completion time objective

In this paper, we study a customer order scheduling problem where a number of orders, composed of several product types, have to be scheduled on a set of parallel machines, each one capable to process a single product type. The objective is to minimise the sum of the completion times of the orders, which is related to the lead time perceived by the customer, and also to the minimisation of the work-in-process. This problem has been previously studied in the literature, and it is known to be NP-hard even for two product types. As a consequence, the interest lies on devising approximate procedures to obtain fast, good performing schedules. Among the different heuristics proposed for the problem, the ECT (Earliest Completion Time) heuristic by Leung et al. [6] has turned to be the most efficient constructive heuristic, yielding excellent results in a wide variety of settings. These authors also propose a tabu search procedure that constitutes the state-of-the-art metaheuristic for the problem. We propose a new constructive heuristic based on a look-ahead mechanism. The computational experience conducted shows that it clearly outperforms ECT, while having both heuristics the same computational complexity. Furthermore, we propose a greedy search algorithm using a specific neighbourhood that outperforms the existing tabu search procedure for different stopping criteria, both in terms of quality of solutions and of required CPU effort.     

一种用于PFSP节能优化的混合禁忌搜索算法

为了追求节能减排与净利润最大化,建立一种置换流水车间订单接受与调度模型。禁忌搜索是一类启发式全局搜索算法,传统禁忌搜索对初始解依赖较大,没有对考虑能效的置换流水车间调度问题进行更深入的优化。鉴于问题的复杂性,提出了一种节能混合禁忌搜索算法,结合了NEH构造启发式算法的优势,并在该算法中设计了订单接受与拒绝编码方式、能耗调整与交货期配置策略。最后采用大量随机实例对性能进行分析。实验结果表明,通过上述改进,改善了算法的全局搜索能力与解决复杂模型的寻优能力,节能混合禁忌搜索较单一算法而言性能更优,可以有效增加企业总净利润,降低能源消耗。     

Artificial intelligence search methods for multi-machine two-stage scheduling with due date penalty,inventory, and machining costs

This paper evaluates artificial intelligence search methods for multi-machine two-stage scheduling problems with due date penalty, inventory, and machining costs. We compare four search methods: tabu search, simulated annealing, genetic algorithm, and neighborhood search. Computational results show that the tabu search performs best in terms of solution quality. The tabu search also requires much less computational time than the genetic algorithm and simulated annealing. As expected, the neighborhood search needs the smallest computational time, but gives the worst solution quality. To further improve the solution quality and computational time, this paper proposes a two-phase tabu search. The two-phase tabu search sequentially addresses two aspects of sequencing for the same problem, order- and component-based sequencing. The order-based tabu search identifies a sequence for customers’ orders. Starting from the sequence identified for customers’ orders, the component-based tabu search fine-tunes the sequence for components produced at the fabrication stage. The results show that the two-phase tabu search is better in solution quality and computational time than the one-phase tabu search. The difference in solution quality is more pronounced at the early stage of the search.Scope and purposeMost manufacturing firms have some form of separate fabrication and assembly stages. Raw materials are transformed into components at the fabrication stage and the components are then assembled into finished products at the assembly stage. The components and assembly items are typically routed in batch quantities through several machines/work centers in a predetermined order before the finished products are delivered to customers.In this study, we model fabrication and assembly work centers as multi-machine two-stage manufacturing systems where a given machine is used to assemble/produce at least one component/product. The scheduling problem considered in this study involves a scheduling decision that achieves three objectives concurrently: (1) meeting customers’ due dates, (2) minimizing inventory cost, and (3) minimizing machining cost. Each order is an indivisible scheduling element that needs to be delivered to customers on the due date. Each order triggers successive production events from upstream to downstream according to the bill-of-material structure between components and end products.The objective of this paper are three-fold: (1) to present a solution representation for the multi-machine two-stage scheduling problem, (2) to identify the best artificial intelligence search method for this problem based on extensive computational experiments, and (3) to propose a modified tabu search method to further improve the solution quality and computational time.     

Family scheduling with batch availability in flow shops to minimize makespan

This paper addresses a batch scheduling problem in flow shop production systems, where job families are formed based on setup similarities. In order to improve setup efficiency, we consider batching decisions in our solution procedure. Due to its high practical relevance, the batch availability assumption is also adopted in this study. In the presence of sequence-dependent setup times, it is proved that a permutation flow shop is generally not optimal. Therefore, our objective is to determine solutions with inconsistent batches, which essentially lead to non-permutation schedules, to minimize makespan. After examining structural properties, we develop a tabu search algorithm with multiple neighbourhood functions. Computational results confirm the remarkable benefits of batching decisions. Our algorithm also outperforms some well-known and well-performing approaches.     

Ant colony optimization for resource-constrained project scheduling

An ant colony optimization (ACO) approach for the resource-constrained project scheduling problem (RCPSP) is presented. Several new features that are interesting for ACO in general are proposed and evaluated. In particular, the use of a combination of two pheromone evaluation methods by the ants to find new solutions, a change of the influence of the heuristic on the decisions of the ants during the run of the algorithm, and the option that an elitist ant forgets the best-found solution are studied. We tested the ACO algorithm on a set of large benchmark problems from the Project Scheduling Library. Compared to several other heuristics for the RCPSP, including genetic algorithms, simulated annealing, tabu search, and different sampling methods, our algorithm performed best on average. For nearly one-third of all benchmark problems, which were not known to be solved optimally before, the algorithm was able to find new best solutions     

Heuristics for the traveling repairman problem with profits

In the traveling repairman problem with profits, a repairman (also known as the server) visits a subset of nodes in order to collect time-dependent profits. The objective consists of maximizing the total collected revenue. We restrict our study to the case of a single server with nodes located in the Euclidean plane. We investigate the properties of this problem, and we derive a mathematical model assuming that the number of nodes to be visited is known in advance. We describe a tabu search algorithm with multiple neighborhoods, we test its performance by running it on instances from the literature and compare the outcomes with an upper bound. We conclude that the tabu search algorithm finds good-quality solutions fast, even for large instances.     

A very fast TS/SA algorithm for the job shop scheduling problem

The job shop scheduling problem (JSP) is one of the most notoriously intractable NP-complete optimization problems. Over the last 10–15 years, tabu search (TS) has emerged as an effective algorithmic approach for the JSP. However, the quality of solutions found by tabu search approach depends on the initial solution. To overcome this problem and provide a robust and efficient methodology for the JSP, the heuristics search approach combining simulated annealing (SA) and TS strategy is developed. The main principle of this approach is that SA is used to find the elite solutions inside big valley (BV) so that TS can re-intensify search from the promising solutions. This hybrid algorithm is tested on the standard benchmark sets and compared with the other approaches. The computational results show that the proposed algorithm could obtain the high-quality solutions within reasonable computing times. For example, 17 new upper bounds among the unsolved problems are found in a short time.     

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

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

A Memetic Approach to the Nurse Rostering Problem

Constructing timetables of work for personnel in healthcare institutions is known to be a highly constrained and difficult problem to solve. In this paper, we discuss a commercial system, together with the model it uses, for this rostering problem. We show that tabu search heuristics can be made effective, particularly for obtaining reasonably good solutions quickly for smaller rostering problems. We discuss the robustness issues, which arise in practice, for tabu search heuristics. This paper introduces a range of new memetic approaches for the problem, which use a steepest descent improvement heuristic within a genetic algorithm framework. We provide empirical evidence to demonstrate the best features of a memetic algorithm for the rostering problem, particularly the nature of an effective recombination operator, and show that these memetic approaches can handle initialisation parameters and a range of instances more robustly than tabu search algorithms, at the expense of longer solution times. Having presented tabu search and memetic approaches (both with benefits and drawbacks) we finally present an algorithm that is a hybrid of both approaches. This technique produces better solutions than either of the earlier approaches and it is relatively unaffected by initialisation and parameter changes, combining some of the best features of each approach to create a hybrid which is greater than the sum of its component algorithms.     

基于混合遗传算法的订单生产调度在机车车辆行业中的应用

机车车辆行业作为典型的面向订单的机械制造企业,优化的生产调度方法能提高订单的准时交货,缩短产品的生产周期,提高企业的市场竞争力。订单生产调度问题是典型的NP-hard问题。遗传算法(Genetic Algorithms)为求具有多个约束的复杂问题提供了有效的方法。但是遗传算法的局部搜索能力比较差,在解决订单生产调度问题中存在着明显的不足。本文引入了局部搜索能力很强的禁忌搜索算法,用遗传算法和禁忌搜索算法相结合的混合遗传算法来解决机车车辆行业中面向订单生产调度问题。     

Acquisition planning and scheduling of computing resources

Cloud computing has been attracting considerable attention since the last decade. This study considers a decision problem formulated from the use of computing services over the Internet. An agent receives orders of computing tasks from his/her clients and on the other hand he/she acquires computing resources from computing service providers to fulfill the requirements of the clients. The processors are bundled as packages according to their speeds and the business strategies of the providers. The packages are rated at a certain pricing scheme to provide flexible purchasing options to the agent. The decision of the agent is to select the packages which can be acquired from the service providers and then schedule the tasks of the clients onto the processors of the acquired packages such that the total cost, including acquisition cost and scheduling cost (total weighted tardiness), is minimized. In this study, we present an integer programming model to formulate the problem and propose several solution methods to produce acquisition and scheduling plans. Ten well-known heuristics of parallel-machine scheduling are adapted to fit into the studied problem so as to provide initial solutions. Tabu search and genetic algorithm are tailored to reflect the problem nature for improving upon the initial solutions. We conduct a series of computational experiments to evaluate the effectiveness and efficiency of all the proposed algorithms. The results of the numerical experiments reveal that the proposed tabu search and genetic algorithm can attain significant improvements.     

A tabu search heuristic for the truck and trailer routing problem

Two new construction heuristics and a tabu search heuristic are presented for the truck and trailer routing problem, a variant of the vehicle routing problem. Computational results indicate that the heuristics are competitive to the existing approaches. The tabu search algorithm obtained better solutions for each of 21 benchmark problems.     

Bottleneck-based heuristics to minimize total tardiness for the flexible flow line with unrelated parallel machines

This paper considers the flexible flow line problem with unrelated parallel machines at each stage and with a bottleneck stage on the line. The objective of the problem is to minimize the total tardiness. Two bottleneck-based heuristics with three machine selection rules are proposed to solve the problem. The heuristics first develop an indicator to identify a bottleneck stage in the flow line, and then separate the flow line into the upstream stages, the bottleneck stage, and the downstream stages. The upstream stages are the stages ahead of the bottleneck stage and the downstream stages are the stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage. Using the new approach, the bottleneck-based heuristics develop two decision rules to iteratively schedule the jobs at the bottleneck stage, the upstream stages, and the downstream stages. In order to evaluate the performance of the bottleneck-based heuristics, seven commonly used dispatching rules and a basic tabu search algorithm are investigated for comparison purposes. Seven experimental factors are used to design 128 production scenarios, and ten test problems are generated for each scenario. Computational results show that the bottleneck-based heuristics significantly outperform all the dispatching rules for the test problems. Although the effective performance of the bottleneck-based heuristics is inferior to the basic tabu search algorithm, the bottleneck-based heuristics are much more efficient than the tabu search algorithm. Also, a test of the effect of the experimental factors on the dispatching rules, the bottleneck-based heuristics, and the basic tabu search algorithm is performed, and some interesting insights are discovered.     

求解流水车间调度问题的混合粒子群算法

针对最小化流水车间调度总完工时间问题,提出了一种混合的粒子群优化算法(Hybrid Particle Swarm Algorithm,HPSA),采用启发式算法产生初始种群,将粒子群算法、遗传操作以及局部搜索策略有效地结合在一起。用Taillard’s基准程序随机产生大量实例,实验结果显示:HPSA通过对种群选取方法的改进和搜索范围的扩大提高了解的质量,在性能上均优于目前较有效的启发式算法和混合的禁忌搜索算法,产生最好解的平均百分比偏差和标准偏差均显著下降,最优解所占比例大幅度提高。     

Order acceptance with weighted tardiness

Over the past decade the strategic importance of order acceptance has been widely recognized in practice as well as academic research. This paper examines order acceptance decisions when capacity is limited, customers receive a discount for late delivery, but early delivery is neither penalized nor rewarded. We model a manufacturing facility that considers a pool of orders, and chooses for processing the subset that results in the highest profit. We present several solution methods, beginning with a straightforward application of an approach which separates sequencing and job acceptance. We then develop an optimal branch-and-bound procedure that uses a linear (integer) relaxation for bounding and performs the sequencing and job acceptance decisions jointly. We develop a variety of fast and high-quality heuristics based on this approach. For small problems, beam search runs almost 20 times faster than the benchmark, with a high degree of accuracy, and a branch-and-bound heuristic using Vogel's method for bounding is over 100 times faster with very high accuracy. For larger problems, a myopic heuristic based on the relaxation runs 2000 times faster than the beam-search benchmark, with comparable accuracy.     

Production scheduling for blocking flowshop in distributed environment using effective heuristics and iterated greedy algorithm

Production scheduling plays an important role in the intelligent decision support system and intelligent optimization decision technology. In the context of the globalization trend, the current production and management may extend from a single factory to a distributed production network. In this paper, we study the distributed blocking flowshop scheduling problem (DBFSP) that is an important generalization of the traditional blocking flowshop scheduling problem in the distributed environment. Six constructive heuristics and an iterated greedy (IG) algorithm are proposed to minimize the makespan, which provides procedures for obtaining efficient and effective solutions to make decision-making sounder. The first five heuristics are developed based on the well-known NEH2 heuristic [B. Naderi, R. Ruiz, The distributed permutation flowshop scheduling problem, Computers & Operations Research, 37 (4) (2010) 754–768.] and the last heuristic is presented by extending the PW heuristic [Q.K. Pan, L. Wang, Effective heuristics for the blocking flowshop scheduling problem with makespan minimization, Omega, 40 (2) (2012) 218–229.] to DBFSP in an effective way. The composite heuristics that combining constructive heuristics and local searches are also studied. The proposed composite heuristics are chosen to generate an initial solution with a high level of quality. Keeping the simplicity of the IG algorithm, three local search procedures, two destruction procedures, an improved reconstruction procedure, and a simulated annealing-like acceptance criterion are well designed based on the problem-specific knowledge to enhance the IG algorithm. The computational experiments are carried out based on the 720 benchmark instances from the literature. The results show that the proposed heuristics are very effective for solving the problem under consideration and the presented IG algorithm performs significantly better than the other state-of-the-art metaheuristics from the literature.     

基于禁忌搜索的启发式任务路径规划算法

基于启发式搜索和禁忌搜索技术,提出一种用于解决有限资源、不同重要性要求的任务路径规划问题的有效算法,通过对不同重要程度的任务进行分层调度,得到较为满意的决策结果.该算法具有搜索空间小、求解速度快的优点.仿真结果验证了算法的有效性.