Bi-objective parallel machines scheduling with sequence-dependent setup times using hybrid metaheuristics and weighted min–max technique

In the literature of multi-objective problem, there are different algorithms to solve different optimization problems. This paper presents a min–max multi-objective procedure for a dual-objective, namely make span, and sum of the earliness and tardiness of jobs in due window machine scheduling problems, simultaneously. In formulation of min–max method when this method is combined with the weighting method, the decision maker can have the flexibility of mixed use of weights and distance parameter to yield a set of Pareto-efficient solutions. This research extends the new hybrid metaheuristic (HMH) to solve parallel machines scheduling problems with sequence-dependent setup time that comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) as an evolutionary algorithm employs certain probability to avoid becoming trapped in a local optimum, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. In addition, two VNS-based HMHs, which are a combination of two methods, SA/VNS and ACO/VNS, are also proposed to solve the addressed scheduling problems. A design of experiments approach is employed to calibrate the parameters. The non-dominated sets obtained from HMH and two best existing bi-criteria scheduling algorithms are compared in terms of various indices and the computational results show that the proposed algorithm is capable of producing a number of high-quality Pareto optimal scheduling plans. Aside, an extensive computational experience is carried out to analyze the different parameters of the algorithm.     

A tabu search algorithm for parallel machine total tardiness problem

In this study, we consider the problem of scheduling a set of independent jobs with sequence dependent setups on a set of uniform parallel machines such that total tardiness is minimized. Jobs have non-identical due dates and arrival times. A tabu search (TS) approach is employed to attack this complex problem. In order to obtain a robust search mechanism, several key components of TS such as candidate list strategies, tabu classifications, tabu tenure and intensification/diversification strategies are investigated. Alternative approaches to each of these issues are developed and extensively tested on a set of problems obtained from the literature. The results obtained are considerably better than those reported previously and constitute the best solutions known for the benchmark problems as to date. Scope and purposeSeveral surveys on parallel machine scheduling with due date related objectives (Oper. Res. 38(1) (1990) 22; EJOR 38 (1989) 156; Oper. Res. 42 (1994) 1025) reveal that the NP-hard nature of the problem renders it a challenging area for many researchers who studied various versions. However, most of these studies make the assumption that jobs are available at the beginning of the scheduling period, which is an important deviation form reality. In this study, as well as distinct due dates and ready times, features such as sequence dependent setup times and different processing rates for machines are incorporated into the classical model. These enhancements approach the model to the actual practice at the expense of complicating the problem further. For this complex problem, we present a tabu search (TS) algorithm to minimize total tardiness and provide the best solutions known for a set of benchmark problems.     

Scheduling unrelated parallel machines with sequence-dependent setups

A methodology for minimizing the weighted tardiness of jobs in unrelated parallel machining scheduling with sequence-dependent setups is presented in this paper. To comply with industrial situations, the dynamic release of jobs and dynamic availability of machines are assumed. Recognizing the inherent difficulty in solving industrial-size problems efficiently, six different search algorithms based on tabu search are developed to identify the best schedule that gives the minimum weighted tardiness. To enhance both the efficiency and efficacy of the search algorithms, four different initial solution finding mechanisms, based on dispatching rules, are developed. While there is no evidence of identifying solutions of better quality by employing a specific initial solution finding mechanism, the use of a specific search algorithm led to identifying solutions of better quality or that required lower computation time, but not both. Based on the extensive statistical analysis performed, the search algorithm with short-term memory and fixed tabu list size is recommended for solving small size problems, while that with long-term memory and minimum frequency for solving medium and large size problems, combined with fixed tabu list size for the former and variable tabu list size for the latter.     

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.     

Bicriteria scheduling problem for unrelated parallel machines with release dates

This research proposes a heuristic and a tabu search algorithm (TSA) to find non-dominated solutions to bicriteria unrelated parallel machine scheduling problems with release dates. The two objective functions considered in this problem are to minimize both makespan and total weighted tardiness. The computational results show that the proposed heuristic is computationally efficient and provides solutions of reasonable quality. The proposed TSA outperforms other algorithms in terms of the number of non-dominated solutions and the quality of its solutions.     

单一模具约束的平行机台成组工作调度方法

本文处理在平行机台上调度具有单一模具约束的成组工作，以最小化总拖期量的问题，研究了最优解的性质，并提出了分枝定界法、启发式算法、多阶段ｔａｂｕｓｅａｒｃｈ算法及组合方法，利用随机问题对各算法进行了对比和分析，获得有实践指导意义的结果。     

An Enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes

This paper addresses a sequence- and machine-dependent batch scheduling problem on a set of unrelated-parallel machines where the objective is to minimize a linear combination of total weighted completion time and total weighted tardiness. In particular, batch scheduling disregards the group technology assumptions by allowing for the possibility of splitting pre-determined groups of jobs into batches with respect to desired lower bounds on batch sizes. With regard to bounds on batch sizes, the MILP model is developed as two integrated batching and scheduling phases to present the problem. A benchmark of small-size instances on group scheduling shows the superior performance of batch scheduling up to 37% reduction in the objective function value. An efficient meta-heuristic algorithm based on tabu search with multi-level diversification and multi-tabu structure is developed at three levels, which moves back and forth between batching and scheduling phases. To eliminate searching in ineffective neighborhoods and thus enhance computational efficiency of search algorithms, several lemmas are proposed and proven. The results of applying lemmas reflect up to 40% reduction in computational times. Comparing the optimal solutions found by CPLEX and tabu search shows that the tabu search algorithm could find solutions, at least as good as CPLEX but in incredibly shorter computational time. In order to trigger the search algorithm, two different initial solution finding mechanisms have been developed and implemented. Also, due to lack of a qualified benchmark for unrelated-parallel machines, a comprehensive data generation mechanism has been developed in a way that it fairly reflects the real world situations encountered in practice. The machine availability times and job release times are considered to be dynamic and the run time of each job differs on different machines based upon the capability of the machines.     

Unrelated parallel machine scheduling with setup times using simulated annealing

This paper presents a scheduling problem for unrelated parallel machines with sequence-dependent setup times, using simulated annealing (SA). The problem accounts for allotting work parts of L jobs into M parallel unrelated machines, where a job refers to a lot composed of N items. Some jobs may have different items while every item within each job has an identical processing time with a common due date. Each machine has its own processing times according to the characteristics of the machine as well as job types. Setup times are machine independent but job sequence dependent. SA, a meta-heuristic, is employed in this study to determine a scheduling policy so as to minimize total tardiness. The suggested SA method utilizes six job or item rearranging techniques to generate neighborhood solutions. The experimental analysis shows that the proposed SA method significantly outperforms a neighborhood search method in terms of total tardiness.     

A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck-tabu search (SB-TS) algorithm by replacing the re-optimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.     

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).     

预制构件并行生产线资源配置与生产调度集成优化

并行生产线和特定工序生产资源共享模式可以显著改善客户满意度并节约成本.针对预制构件并行生产线资源配置与生产调度集成优化问题,基于分解策略和交替迭代优化思想,提出一种交替式混合果蝇-禁忌搜索算法(AHFOA＿TS)以最小化拖期惩罚费用.首先,通过快速启发式方法产生一较好初始解;然后,固定资源配置方案,为提高算法局部搜索能力,通过集成多种局部搜索方式,设计一种离散果蝇优化算法优化订单指派及调度方案;最后,固定订单指派及调度方案,为减少无效搜索次数,设计一种基于双层变异算子和精英劣解交叉策略的混合禁忌搜索算法以优化资源配置方案,如此两个阶段交替运行直至满足终止条件.此外,设计4种基于交替搜索框架的智能优化算法用于比较.计算结果表明, AHFOA＿TS算法能够更有效求解预制构件生产线资源配置和生产调度集成优化问题.     

Genetic tabu search for the fuzzy flexible job shop problem

This paper tackles the flexible job-shop scheduling problem with uncertain processing times. The uncertainty in processing times is represented by means of fuzzy numbers, hence the name fuzzy flexible job-shop scheduling. We propose an effective genetic algorithm hybridised with tabu search and heuristic seeding to minimise the total time needed to complete all jobs, known as makespan. To build a high-quality and diverse set of initial solutions we introduce a heuristic method which benefits from the flexible nature of the problem. This initial population will be the starting point for the genetic algorithm, which then applies tabu search to every generated chromosome. The tabu search algorithm relies on a neighbourhood structure that is proposed and analysed in this paper; in particular, some interesting properties are proved, such as feasibility and connectivity. Additionally, we incorporate a filtering mechanism to reduce the neighbourhood size and a method that allows to speed-up the evaluation of new chromosomes. To assess the performance of the resulting method and compare it with the state-of-the-art, we present an extensive computational study on a benchmark with 205 instances, considering both deterministic and fuzzy instances to enhance the significance of the study. The results of these experiments clearly show that not only does the hybrid algorithm benefit from the synergy among its components but it is also quite competitive with the state-of-the-art when solving both crisp and fuzzy instances, providing new best-known solutions for a number of these test 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.     

Capacitated Clustering Problems by Hybrid Simulated Annealing and Tabu Search

The capacitated clustering problem (CCP) is the problem in which a given set of weighted objects is to be partitioned into clusters so that the total weight of objects in each cluster is less than a given value (cluster ‘capacity’). The objective is to minimize the total scatter of objects from the ‘centre’ of the cluster to which they have been allocated. A simple constructive heuristic, a R-interchange generation mechanism, a hybrid simulated annealing (SA) and tabu search (TS) algorithm which has computationally desirable features using a new non-monotonic cooling schedule, are developed. A classification of the existing SA cooling schedules is presented. The effects on the final solution quality of the initial solutions, the cooling schedule parameters and the neighbourhood search strategies are investigated. Computational results on randomly generated problems with size ranging from 50 to 100 customers indicate that the hybrid SA/TS algorithm out-performs previous simulated annealing algorithms, a simple tabu search and local descent algorithms.     

A population-based variable neighborhood search for the single machine total weighted tardiness problem

This paper investigates the single machine total weighted tardiness problem, in which a set of independent jobs with distinct processing times, weights, and due dates are to be scheduled on a single machine to minimize the sum of weighted tardiness of all jobs. This problem is known to be strongly NP-hard, and thus provides a challenging area for metaheuristics. A population-based variable neighborhood search (PVNS) algorithm is developed to solve it. This algorithm differs from the basic variable neighborhood search (VNS). First, the PVNS consists of a number of iterations of the basic VNS, and in each iteration a population of solutions is used to simultaneously generate multiple trial solutions in a neighborhood so as to improve the search diversification. Second, the PVNS adopts a combination of path-relinking, variable depth search and tabu search to act as the local search procedure so as to improve the search intensification. Computational experiments show that the proposed PVNS algorithm can obtain the optimal or best known solutions within a reasonable computation time for all standard benchmark problem instances from the literature.     

Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time

In this paper, we present filtered and recovering beam search algorithms for the single machine earliness/tardiness scheduling problem with no idle time, and compare them with existing neighbourhood search and dispatch rule heuristics. Filtering procedures using both priority evaluation functions and problem-specific properties have been considered.The computational results show that the recovering beam search algorithms outperform their filtered counterparts, while the priority-based filtering procedure proves superior to the rules-based alternative. The best solutions are given by the neighbourhood search algorithm, but this procedure is computationally intensive and can only be applied to small or medium size instances. The recovering beam search heuristic provides results that are close in solution quality and is significantly faster, so it can be used to solve even large problems.     

Block approach—tabu search algorithm for single machine total weighted tardiness problem

Problem of scheduling on a single machine to minimize total weighted tardiness of jobs can be described as follows: there are n jobs to be processed, each job has an integer processing time, a weight and a due date. The objective is to minimize the total weighted tardiness of jobs. The problem belongs to the class of NP-hard problems. Some new properties of the problem associated with the blocks have been presented and discussed. These properties allow us to propose a new fast local search procedure based on a tabu search approach with a specific neighborhood which employs blocks of jobs and a compound moves technique. A compound move consists in performing several moves simultaneously in a single iteration of algorithm and allows us to accelerate the convergence to good solutions. In the algorithm, we use an idea which decreases the complexity for the search of neighborhood from O(n³) to O(n²). Additionally, the neighborhood is reduced by using some elimination criteria. The method presented in this paper is deterministic one and has not any random element, as distinct from other effective but non-deterministic methods proposed for this problem, such as tabu search of Crauwels, H. A. J., Potts, C. N., & Van Wassenhove, L. N. (1998). Local search heuristics for the single machine total weighted tardiness Scheduling Problem. INFORMS Journal on Computing, 10(3), 341–350, iterated dynasearch of Congram, R. K., Potts C. N., & Van de Velde, S. L. (2002). An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS Journal on Computing, 14(1), 52–67 and enhanced dynasearch of Grosso, A., Della Croce, F., & Tadei, R. (2004). An enhanced dynasearch neighborhood for single-machine total weighted tardiness scheduling problem. Operations Research Letters, 32, 68–72. Computational experiments on the benchmark instances from OR-Library (http://people.brunel.ac.uk/mastjjb/jeb/info.html) are presented and compared with the results yielded by the best algorithms discussed in the literature. These results show that the algorithm proposed allows us to obtain the best known results for the benchmarks in a short time. The presented properties and ideas can be applied in any local search procedures.     

Modeling machine loading problem of FMSs and its solution methodology using a hybrid tabu search and simulated annealing-based heuristic approach

In this article, a machine loading problem of a flexible manufacturing system (FMS) is discussed having the bicriterion objectives of minimizing system unbalance and maximizing throughput in the presence of technological constraints such as available machining time and tool slots. A generic 0–1 integer programming formulation with the objective functions and constraints described above has been proposed. A hybrid algorithm based on tabu search and simulated annealing (SA) is employed to solve the problem. The main advantage of this approach is that a short-term memory provided by the tabu list can be used to avoid revisiting the solution while preserving the stochastic nature of the SA method. The proposed methodology has been tested on ten standard problems and the results obtained are compared with those from some of the existing heuristics.     

带作业范围约束的岸桥调度模型及其算法设计

受电缆线坑位置与缆线长度的限制,岸桥作业只能在一定的横向移动范围之内。考虑到这一现实要求,结合岸桥作业禁止跨越与安全距离等特有约束,以最小化装卸作业的makespan为目标,构建了新的岸桥作业调度混合整数规划模型。针对问题的NP-hard特性,设计了一种混合模拟退火算法,运用启发式算法生成质量较高的初始解,结合遗传算法的变异运算生成邻域新解,增强了解的多样性,引入禁忌搜索算法的禁忌表操作,避免了循环搜索,提高了求解效率。大规模实验结果表明所建立的模型是有效的,算法的求解质量与效率明显优于标准模拟退火算法与禁忌搜索算法。当实验规模逐渐增大时,与LINGO软件相比,算法在求解效率方面的优势越来越明显。     

约束满足混合算法求解提前/拖期Job Shop调度问题

针对提前/拖期Job Shop调度问题,建立其约束满足优化问题模型,提出了一种约束满足与禁忌搜索结合的混合算法。该算法基于约束满足思想,通过约束传播技术和启发式修复算法,得到可行调度作为禁忌搜索算法的初始解;再进行关键路径上的邻域变换,优化当前解;并采用一种全局邻域交换策略,扩大搜索空间,改善优化结果。数据实验表明了该混合算法的可行性和有效性。