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.