Makespan minimization for scheduling unrelated parallel machines with setup times

This study considers the problem of scheduling jobs on unrelated parallel machines with machine-dependent and job sequence-dependent setup times. In this study, a restricted simulated annealing (RSA) algorithm which incorporates a restricted search strategy is presented to minimize the makespan. The proposed RSA algorithm can effective reduce the search effort required to find the best neighborhood solution by eliminating ineffective job moves. The effectiveness and efficiency of the proposed RSA algorithm is compared with the basic simulated annealing and existing meta-heuristics on a benchmark problem dataset used in earlier studies. Computational results indicate that the proposed RSA algorithm compares well with the state-of-the-art meta-heuristic for small-sized problems, and significantly outperforms basic simulated annealing algorithm and existing algorithms for large-sized problems.     

A hybrid artificial immune algorithm for a realistic variant of job shops to minimize the total completion time

This paper investigates an extended problem of job shop scheduling to minimize the total completion time. With aim of actualization of the scheduling problems, many researchers have recently considered realistic assumptions in their problems. Two of the most applied assumptions are to consider sequence-dependent setup times and machine availability constraints (MACs). In this paper, we deal with a specific case of MACs caused by preventive maintenance (PM) operations. Contrary to the previous papers considering fixed or/and conservative policies, we consider flexible PM operations, in which PM operations may be postponed or expedited as required. A simple technique is employed to schedule production jobs along with the flexible MACs caused by PM. To solve the given problem, we present a novel meta-heuristic method based on the artificial immune algorithm (AIA) incorporating some advanced features. For further enhancement, the proposed AIA is hybridized with a simple and fast simulated annealing (SA). To evaluate the proposed algorithms, we compare our proposed AIA with three well-known algorithms taken from the literature. Finally, we find that the proposed AIA outperforms other algorithms.     

A knowledge-based archive multi-objective simulated annealing algorithm to optimize series–parallel system with choice of redundancy strategies

Redundancy allocation problem (RAP) is one of the best-developed problems in reliability engineering studies. This problem follows to optimize the reliability of a system containing s sub-systems under different constraints, including cost, weight, and volume restrictions using redundant components for each sub-system. Various solving methodologies have been used to optimize this problem, including exact, heuristic, and meta-heuristic algorithms. In this paper, an efficient multi-objective meta-heuristic algorithm based on simulated annealing (SA) is developed to solve multi-objective RAP (MORAP). This algorithm is knowledge-based archive multi-objective simulated annealing (KBAMOSA). KBAMOSA applies a memory matrix to reinforce the neighborhood structure to achieve better quality solutions. The results analysis and comparisons demonstrate the performance of the proposed algorithm for solving MORAP.     

An integrated search heuristic for large-scale flexible job shop scheduling problems

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop scheduling problem (JSP), where each operation is allowed to be processed by any machine from a given set, rather than one specified machine. In this paper, two algorithm modules, namely hybrid harmony search (HHS) and large neighborhood search (LNS), are developed for the FJSP with makespan criterion. The HHS is an evolutionary-based algorithm with the memetic paradigm, while the LNS is typical of constraint-based approaches. To form a stronger search mechanism, an integrated search heuristic, denoted as HHS/LNS, is proposed for the FJSP based on the two algorithms, which starts with the HHS, and then the solution is further improved by the LNS. Computational simulations and comparisons demonstrate that the proposed HHS/LNS shows competitive performance with state-of-the-art algorithms on large-scale FJSP problems, and some new upper bounds among the unsolved benchmark instances have even been found.     

基数约束投资组合问题的一种混合元启发式算法求解

针对资产数目和投资资金比例受约束的投资组合选择这一NP难问题,基于混沌搜索、粒子群优化和引力搜索算法提出了一种新的混合元启发式搜索算法。该算法能很好地平衡开发能力和勘探能力,有效抑制了算法早熟收敛现象。标准测试函数的测试结果表明混合算法与标准的粒子群优化和引力搜索算法相比具有更好的寻优效率;实证分析进一步对混合算法与遗传算法及粒子群优化算法在求解这类投资组合选择问题的性能进行了比较。数值结果表明,混合算法在搜索具有高预期回报的非支配投资组合方面表现更好,取得了更为满意的结果。     

Annealing-based heuristics and genetic algorithms for circuit partitioning in parallel test generation

In this paper simulated annealing and genetic algorithms are applied to the graph partitioning problem. These techniques mimic processes in statistical mechanics and biology, respectively, and are the most popular meta-heuristics or general-purpose optimization strategies. A hybrid algorithm for circuit partitioning, which uses tabu search to improve the simulated annealing meta-heuristics, is also proposed and compared with pure tabu search and simulated annealing algorithms, and also with a genetic algorithm. The solutions obtained are compared and evaluated by including the hybrid partitioning algorithm in a parallel test generator which is used to determine the test patterns for the circuits of the frequently used ISCAS benchmark set.     

Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints

One of the common assumptions in the field of scheduling is that machines are always available in the planning horizon. This may not be true in realistic problems since machines might be busy processing some jobs left from previous production horizon, breakdowns or preventive maintenance activities. Another common assumption is the consideration of setup times as a part of processing times, while in some industries, such as printed circuit board and automobile manufacturing, not only setups are an important factor but also setup magnitude of a job depends on its immediately preceding job on the same machine, known as sequence-dependent setup times. In this paper, we consider hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints caused by preventive maintenance. The optimization criterion is the minimization of makespan. Since this problem is NP-hard in the strong sense, we propose three heuristics, based on SPT, LPT and Johnson rule and two metaheuristics based on genetic algorithm and simulated annealing. Computational experiments are performed to evaluate the efficiencies of the algorithms.     

Using meta-heuristics for project scheduling under mode identity constraints

Mode identity and resource constrained project scheduling problem (MIRCPSP) is a substantial generalization of the well-known multi-mode problem. It arises when certain activities in the project are interdependent. That is, the set of all activities in the project are partitioned into disjoint subsets where all activities forming one subset have to be processed in the same mode. This paper addresses project scheduling problem with resource and mode identity constraints to minimize the project makespan. This problem is strongly NP-hard and three meta-heuristic algorithms namely imperialist competitive algorithm, simulated annealing and differential evolution are proposed to solve it. In order to improve the quality of the employed algorithms a local search and learning module is combined with the meta-heuristic algorithms. The performance of the algorithms is evaluated on 180 test problems by statistically comparing their solution in term of the objective function and computational times. The obtained computational results indicate that the integration of the learning module and the proposed algorithm is efficient and effective.     

Solving the team orienteering problem using effective multi-start simulated annealing

The team orienteering problem (TOP) is known as an NP-complete problem. A set of locations is provided and a score is collected from the visit to each location. The objective is to maximize the total score given a fixed time limit for each available tour. Given the computational complexity of this problem, a multi-start simulated annealing (MSA) algorithm which combines a simulated annealing (SA) based meta-heuristic with a multi-start hill climbing strategy is proposed to solve TOP. To verify the developed MSA algorithm, computational experiments are performed on well-known benchmark problems involving numbers of locations ranging between 42 and 102. The experimental results demonstrate that the multi-start hill climbing strategy can significantly improve the performance of the traditional single-start SA. Meanwhile, the proposed MSA algorithm is highly effective compared to the state-of-the-art meta-heuristics on the same benchmark instances. The proposed MSA algorithm obtained 135 best solutions to the 157 benchmark problems, including five new best solutions. In terms of both solution quality and computational expense, this study successfully constructs a high-performance method for solving this challenging problem.     

Two meta-heuristic algorithms for two-echelon location-routing problem with vehicle fleet capacity and maximum route length constraints

In the present research, a two-echelon location-routing problem with constraints of vehicle fleet capacity and maximum route length is considered. The problem’s objective is to determine the location and number of two types of capacitated facilities, the size of two different vehicle fleets, and the related routes on each echelon. Two algorithms hybrid genetic algorithm and simulated annealing are then applied to solve the problem. Results of numerical experiments show that the applied hybrid genetic and simulated annealing algorithms are much more effective than the solutions of the solved examples by the software LINGO. Finally, solutions of simulated annealing and hybrid genetic algorithms were compared with each other.     

A grasp algorithm for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness

In this paper we address the problem of minimizing the weighted sum of makespan and maximum tardiness in an m-machine flow shop environment. This is a NP-hard problem in the strong sense. An attempt has been made to solve this problem using a metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP). GRASP is a competitive algorithm and is a meta-heuristic for solving combinatorial optimization problems. We have customized the basic concepts of GRASP algorithm to solve a bicriteria flow shop problem and a new algorithm named B-GRASP (Bicriteria GRASP algorithm) is proposed. The new proposed algorithm is evaluated using benchmark problems taken from Taillard and compared with the existing simulated annealing based heuristic developed by Chakravarthy and Rajendran. Computational experiments indicate that the proposed algorithm is much better than the existing one in all cases.     

A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion

This paper investigates the limited-buffer permutation flow shop scheduling problem (LBPFSP) with the makespan criterion. A hybrid variable neighborhood search (HVNS) algorithm hybridized with the simulated annealing algorithm is used to solve the problem. A method is also developed to decrease the computational effort needed to implement different types of local search approaches used in the HVNS algorithm. Computational results show the higher efficiency of the HVNS algorithm as compared with the state-of-the-art algorithms. In addition, the HVNS algorithm is competitive with the algorithms proposed in the literature for solving the blocking flow shop scheduling problem (i.e., LBPFSP with zero-capacity buffers), and finds 54 new upper bounds for the Taillard's benchmark instances.     

A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows

The Capacitated Vehicle Routing Problem with Time Windows is an important combinatorial optimization problem consisting in the determination of the set of routes of minimum distance to deliver goods, using a fleet of identical vehicles with restricted capacity, so that vehicles must visit customers within a time frame. A large number of algorithms have been proposed to solve single-objective formulations of this problem, including meta-heuristic approaches, which provide high quality solutions in reasonable runtimes. Nevertheless, in recent years some authors have analyzed multi-objective variants that consider additional objectives to the distance travelled. This paper considers not only the minimum distance required to deliver goods, but also the workload imbalance in terms of the distances travelled by the used vehicles and their loads. Thus, MMOEASA, a Pareto-based hybrid algorithm that combines evolutionary computation and simulated annealing, is here proposed and analyzed for solving these multi-objective formulations of the VRPTW. The results obtained when solving a subset of Solomon’s benchmark problems show the good performance of this hybrid approach.     

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.     

Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems

Earliness/tardiness scheduling problems with undetermined common due date which have wide application background in textile industry, mechanical industry, electronic industry and so on, are very important in the research fields such as industry engineering and CIMS. In this paper, a kind of genetic algorithm based on sectional code for minimizing the total cost of assignment of due date, earliness and tardiness in this kind of scheduling problem is proposed to determine the optimal common due date and the optimal scheduling policy for determining the job number and their processing order on each machine. Also, simulated annealing mechanism and the iterative heuristic fine-tuning operator are introduced into the genetic algorithm so as to construct three kinds of hybrid genetic algorithms with good performance. Numerical computational results focusing on the identical parallel machine scheduling problem and the general parallel machine scheduling problem shows that these algorithms outperform heuristic procedures, and fit for larger scale parallel machine earliness/tardiness scheduling problem. Moreover, with practical application data from one of the largest cotton colored weaving enterprises in China, numerical computational results show that these genetic algorithms are effective and robust, and that especially the performance of the hybrid genetic algorithm based on simulated annealing and the iterative heuristic fine-tuning operator is the best among them.     

Integrating non-preemptive open shops scheduling with sequence-dependent setup times using advanced metaheuristics

In this article, we consider non-preemptive open shops scheduling problem (OSSP) where setup times are sequence-dependent (SDST) on each machine to minimize makespan. The contributions of this article are threefold. Firstly, we incorporate a very practical assumption in our problem, SDST, which, according to Allahverdi et al. (2008) [Allahverdi, A., Ng, C. T., Cheung, T. C. E., & Kovalyov, Y. M. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), 985–1032], no paper has ever attempted to integrate into OSSP. Secondly, we propose two new advanced metaheuristics: multi-neighborhood search simulated annealing and hybrid simulated annealing to tackle the problem at hand. Thirdly, for the first time, we adapt two well-known constructive heuristics: longest total processing time and longest total remaining processing from the literature so as to consider the case of SDSTs. We also apply genetic algorithm from the literature of OSSP to embrace the concepts of SDST. Since there is no standard SDST-OSSP benchmark, we make certain adaptations on the Taillard’s benchmark [Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278–285] to include setup times. An experimental design based on foregoing benchmark is conducted to evaluate the competitiveness and robustness of our proposed algorithm against some effective algorithms in the literature. The obtained results strongly support the high performance of our proposed algorithms with respect to other well-known heuristic and metaheuristic algorithms.     

A simulated annealing‐based maximum‐margin clustering algorithm

Maximum‐margin clustering is an extension of the support vector machine (SVM) to clustering. It partitions a set of unlabeled data into multiple groups by finding hyperplanes with the largest margins. Although existing algorithms have shown promising results, there is no guarantee of convergence of these algorithms to global solutions due to the nonconvexity of the optimization problem. In this paper, we propose a simulated annealing‐based algorithm that is able to mitigate the issue of local minima in the maximum‐margin clustering problem. The novelty of our algorithm is twofold, ie, (i) it comprises a comprehensive cluster modification scheme based on simulated annealing, and (ii) it introduces a new approach based on the combination of k‐means++ and SVM at each step of the annealing process. More precisely, k‐means++ is initially applied to extract subsets of the data points. Then, an unsupervised SVM is applied to improve the clustering results. Experimental results on various benchmark data sets (of up to over a million points) give evidence that the proposed algorithm is more effective at solving the clustering problem than a number of popular clustering algorithms.     

An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness

In this communication, we strive to apply a novel simulated annealing to consider scheduling hybrid flowshop problems to minimize both total completion time and total tardiness. To narrow the gap between the theory and the practice of the hybrid flowshop scheduling, we integrate two realistic and practical assumptions which are sequence-dependent setup and transportation times into our problem. We apply a metaheuristic based on simulated annealing (SA) which strikes a compromise between intensification and diversification mechanisms to augment the competitive performance of our proposed SA. A comprehensive calibration of different parameters and operators are done. We employ Taguchi method to select the optimum parameters with the least possible number of experiments. For the purpose of performance evaluation of our proposed algorithm, we generate a benchmark against which the adaptations of high performing algorithms in the literature are brought into comparison. Moreover, we investigate the impacts of increase of number of jobs on the performance of our algorithm. The efficiency and effectiveness of our hybrid simulated annealing are inferred from all the computational results obtained in various situations.     

Memetic algorithm with node and edge histogram for no-idle flow shop scheduling problem to minimize the makespan criterion

This paper presents a memetic algorithm with hybrid node and edge histogram (MANEH) to solve no-idle permutation flow shop scheduling problem (NIPFSP) with the criterion to minimize the maximum completion time (the makespan criterion). The MANEH mainly composes of two components: population-based global search and local refinements for individuals. At the initialization stage, a modified speed-up NEH method and the random initialization are utilized to generate more promising solutions with a reasonable running time. At the population-based global search stage, a random sample crossover is first proposed to construct a hybrid node and edge histogram matrix (NEHM) with superior solutions in the population, and then a new sequence is generated by sampling the NEHM or selecting jobs from a template sequence. At the local refinements stage, an improved general variable neighborhood search with the simulated annealing acceptance (GVNS-SA) is developed to improve the current best individual. The GVNS-SA adopts a random referenced local search in the inner loop and the probability of SA to decide whether accept the incumbent solution for the next iteration. Moreover, the influence of key parameters in the MANEH is investigated based on the approach of a design of experiments (DOE). Finally, numerical simulation based on the benchmark of Ruiz and thorough statistical analysis are provided. The comparisons between MANEH and some existing algorithms as well as MA-based algorithms demonstrate the effectiveness and superiority of the proposed MANEH in solving the NIPFSP. Furthermore, the MANEH improves 89 out of the 250 current best solutions reported in the literature.     

A new chaotic multi-verse optimization algorithm for solving engineering optimization problems

Multi-verse optimization algorithm (MVO) is one of the recent meta-heuristic optimization algorithms. The main inspiration of this algorithm came from multi-verse theory in physics. However, MVO like most optimization algorithms suffers from low convergence rate and entrapment in local optima. In this paper, a new chaotic multi-verse optimization algorithm (CMVO) is proposed to overcome these problems. The proposed CMVO is applied on 13 benchmark functions and 7 well-known design problems in the engineering and mechanical field; namely, three-bar trust, speed reduce design, pressure vessel problem, spring design, welded beam, rolling element-bearing and multiple disc clutch brake. In the current study, a modified feasible-based mechanism is employed to handle constraints. In this mechanism, four rules were used to handle the specific constraint problem through maintaining a balance between feasible and infeasible solutions. Moreover, 10 well-known chaotic maps are used to improve the performance of MVO. The experimental results showed that CMVO outperforms other meta-heuristic optimization algorithms on most of the optimization problems. Also, the results reveal that sine chaotic map is the most appropriate map to significantly boost MVO’s performance.