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.     

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.     

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

针对资产数目和投资资金比例受约束的投资组合选择这一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.     

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.