A comparison of two chromosome representation schemes used in solving a family-based scheduling problem

Meta-heuristic algorithms have been widely used in solving scheduling problems; previous studies focused on enhancing existing algorithmic mechanisms. This study advocates a new perspective—developing new chromosome (solution) representation schemes may improve the performance of existing meta-heuristic algorithms. In the context of a scheduling problem, known as permutation manufacturing-cell flow shop (PMFS), we compare the effectiveness of two chromosome representation schemes (S_old and S_new) while they are embedded in a meta-heuristic algorithm to solve the PMFS scheduling problem. Two existing meta-heuristic algorithms, genetic algorithm (GA) and ant colony optimization (ACO), are tested. Denote a tested meta-heuristic algorithm by X_Y, where X represents an algorithmic mechanism and Y represents a chromosome representation. Experiment results indicate that GA_ S_new outperforms GA_S_old, and ACO_S_new also outperforms ACO_S_old. These findings reveal the importance of developing new chromosome representations in the application of meta-heuristic algorithms.     

Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems

This paper attempts to compare the effect of using different chromosome representations while developing a genetic algorithm to solve a scheduling problem called DFJS (distributed flexible job shop scheduling) problem. The DFJS problem is strongly NP-hard; most recent prior studies develop various genetic algorithms (GAs) to solve the problems. These prior GAs are similar in the algorithmic flows, but are different in proposing different chromosome representations. Extending from this line, this research proposes a new chromosome representation (called S_OP) and develops a genetic algorithm (called GA_OP) to solve the DFJS problem. Experiment results indicate that GA_OP outperforms all prior genetic algorithms. This research advocates the importance of developing appropriate chromosome representations while applying genetic algorithms (or other meta-heuristic algorithms) to solve a space search problem, in particular when the solution space is high-dimensional.     

Solving the bi-objective personnel assignment problem using particle swarm optimization

A particle swarm optimization (PSO) algorithm combined with the random-key (RK) encoding scheme (named as PSORK) for solving a bi-objective personnel assignment problem (BOPAP) is presented. The main contribution of this work is to improve the f₁_f₂ heuristic algorithm which was proposed by Huang et al. [3]. The objective of the f₁_f₂ heuristic algorithm is to get a satisfaction level (SL) value which is satisfied to the bi-objective values f₁, and f₂ for the personnel assignment problem. In this paper, PSORK algorithm searches the solution of BOPAP space thoroughly. The experimental results show that the solution quality of BOPAP based on the proposed method is far better than that of the f₁_f₂ heuristic algorithm.     

Improved LP-based algorithms for the closest string problem

In a recent paper by Liu et al. [Exact algorithm and heuristic for the closest string problem, Computers & Operations Research 2011;38:1513-20], a polynomial time heuristic procedure is proposed for the closest string problem (CSP). Such heuristic called LDDA_LSS is a combination of a previously published approximation algorithm and local search strategies. This paper points out that an instant algorithm deriving a feasible solution directly from the continuous relaxation solution of a standard ILP formulation of CSP already strongly outperforms LDDA_LSS both in terms of solution quality and computing time. Two core based procedures are then proposed that further improve the results of the instant algorithm. Based on these results, we conclude that such LP-based approaches for their efficiency and simplicity should be used as a benchmark for future heuristics on CSP.     

An ACO algorithm for makespan minimization in parallel batch machines with non-identical job sizes and incompatible job families

We study the problem of scheduling a set of N jobs with non-identical job sizes from F different families on a set of M parallel batch machines; the objective is to minimize the makespan. The problem is known to be NP-hard. A meta-heuristic based on Max–Min Ant System (MMAS) is presented. The performance of the algorithm is compared with several previously studied algorithms by computational experiments. According to our results, the average distance between the solutions found by our proposed algorithm and the lower bounds is about 4% less than that of the best of all the compared algorithms, demonstrating that our algorithm outperforms the previously studied algorithms.     

Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems

In our previous researches, we proposed the artificial chromosomes with genetic algorithm (ACGA) which combines the concept of the Estimation of Distribution Algorithms (EDAs) with genetic algorithms (GAs). The probabilistic model used in the ACGA is the univariate probabilistic model. We showed that ACGA is effective in solving the scheduling problems. In this paper, a new probabilistic model is proposed to capture the variable linkages together with the univariate probabilistic model where most EDAs could use only one statistic information. This proposed algorithm is named extended artificial chromosomes with genetic algorithm (eACGA). We investigate the usefulness of the probabilistic models and to compare eACGA with several famous permutation-oriented EDAs on the benchmark instances of the permutation flowshop scheduling problems (PFSPs). eACGA yields better solution quality for makespan criterion when we use the average error ratio metric as their performance measures. In addition, eACGA is further integrated with well-known heuristic algorithms, such as NEH and variable neighborhood search (VNS) and it is denoted as eACGA_hybrid to solve the considered problems. No matter the solution quality and the computation efficiency, the experimental results indicate that eACGA_hybrid outperforms other known algorithms in literature. As a result, the proposed algorithms are very competitive in solving the PFSPs.     

Coupling Genetic Local Search and Recovering Beam Search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates

In this paper we consider the well-known single machine scheduling problem with release dates and minimization of the total job completion time. For solving this problem, denoted by 1|r_j|∑C_j, we provide a new metaheuristic which is an extension of the so-called filtered beam search proposed by Ow and Morton [30]. This metaheuristic, referred to as a Genetic Recovering Beam Search (GRBS), takes advantages of a Genetic Local Search (GLS) algorithm and a Recovering Beam Search (RBS) in order to efficiently explore the solution space. In this paper we present the GRBS framework and its application to the 1|r_j|∑C_j problem. Computational results show that it consistently yields optimal or near-optimal solutions and that it provides interesting results by comparison to GLS and RBS algorithms. Moreover, these results highlight that the proposed algorithm outperforms the state-of-the-art heuristics.     

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 improved ant colony optimization algorithm for nonlinear resource-leveling problems

The notion of using a meta-heuristic approach to solve nonlinear resource-leveling problems has been intensively studied in recent years. Premature convergence and poor exploitation are the main obstacles for the heuristic algorithms. Analyzing the characteristics of the project topology network, this paper introduces a directional ant colony optimization (DACO) algorithm for solving nonlinear resource-leveling problems. The DACO algorithm introduced can efficiently improve the convergence rate and the quality of solution for real-project scheduling.     

Optimizing a bi-objective multi-product EPQ model with defective items,rework and limited orders: NSGA-II and MOPSO algorithms

In this paper, a bi-objective multi-products economic production quantity (EPQ) model is developed, in which the number of orders is limited and imperfect items that are re-workable are produced. The objectives of the problem are minimization of the total inventory costs as well as minimizing the required warehouse space. The model is shown to be of a bi-objective nonlinear programming type, and in order to solve it two meta-heuristic algorithms namely, the non-dominated sorting genetic algorithm (NSGA-II) and multi-objective particle swarm optimization (MOPSO) algorithm, are proposed. To verify the solution obtained and to evaluate the performance of proposed algorithms, two-sample t-tests are employed to compare the means of the first objective value, the means of the second objective values, and the mean required CPU time of solving the problem using two algorithms. The results show while both algorithms are efficient to solve the model and the solution qualities of the two algorithms do not differ significantly, the computational CPU time of MOPSO is considerably lower than that of NSGA-II.     

A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem

In this paper, a novel multi-objective location model within multi-server queuing framework is proposed, in which facilities behave as M/M/m queues. In the developed model of the problem, the constraints of selecting the nearest-facility along with the service level restriction are considered to bring the model closer to reality. Three objective functions are also considered including minimizing (I) sum of the aggregate travel and waiting times, (II) maximum idle time of all facilities, and (III) the budget required to cover the costs of establishing the selected facilities plus server staffing costs. Since the developed model of the problem is of an NP-hard type and inexact solutions are more probable to be obtained, soft computing techniques, specifically evolutionary computations, are generally used to cope with the lack of precision. From different terms of evolutionary computations, this paper proposes a Pareto-based meta-heuristic algorithm called multi-objective harmony search (MOHS) to solve the problem. To validate the results obtained, two popular algorithms including non-dominated sorting genetic algorithm (NSGA-II) and non-dominated ranking genetic algorithm (NRGA) are utilized as well. In order to demonstrate the proposed methodology and to compare the performances in terms of Pareto-based solution measures, the Taguchi approach is first utilized to tune the parameters of the proposed algorithms, where a new response metric named multi-objective coefficient of variation (MOCV) is introduced. Then, the results of implementing the algorithms on some test problems show that the proposed MOHS outperforms the other two algorithms in terms of computational time.     

A new particle swarm feature selection method for classification

Searching for an optimal feature subset from a high-dimensional feature space is an NP-complete problem; hence, traditional optimization algorithms are inefficient when solving large-scale feature selection problems. Therefore, meta-heuristic algorithms are extensively adopted to solve such problems efficiently. This study proposes a regression-based particle swarm optimization for feature selection problem. The proposed algorithm can increase population diversity and avoid local optimal trapping by improving the jump ability of flying particles. The data sets collected from UCI machine learning databases are used to evaluate the effectiveness of the proposed approach. Classification accuracy is used as a criterion to evaluate classifier performance. Results show that our proposed approach outperforms both genetic algorithms and sequential search algorithms.     

Earliness–tardiness minimization on a single machine to schedule preventive maintenance tasks: metaheuristic and exact methods

In this paper, we consider the problem of scheduling a set of M preventive maintenance tasks to be performed on M machines. The machines are assigned to execute production tasks. We aim to minimize the total preventive maintenance cost such that the maintenance tasks have to continuously be run during the schedule horizon. Such a constraint holds when the maintenance resources are not sufficient. We solve the problem by two exact methods and meta-heuristic algorithms. As exact procedures we used linear programming and branch and bound methods. As meta-heuristics, we propose a local search approach as well as a genetic algorithm. Computational experiments are performed on randomly generated instances to show that the proposed methods produce appropriate solutions for the problem. The computational results show that the deviation of the meta-heuristics solutions to the optimal one is very small, which confirms the effectiveness of meta-heuristics as new approaches for solving hard scheduling problems.     

Optimization of production time in the multi-pass milling process via a Robust Grey Wolf Optimizer

In order to optimize multi-pass milling process, selection of optimal values for the parameters of the process is of great importance. The mathematical model for optimization of multi-pass milling process is a multi-constrained nonlinear programing formulation which is hard to be solved. Therefore, a novel robust meta-heuristic algorithm named Robust Grey Wolf Optimizer (RGWO) is proposed. In order to develop a RGWO, a robust design methodology named Taguchi method is utilized to tune the parameters of the algorithm. Therefore, in contradiction to previous researches, there is no need to design costly experiments to obtain the optimal values of the parameters of the GWO. In addition, an efficient constraint handling approach is implemented to handle complex constraints of the problem. A real-world problem is adopted to show the effectiveness and efficiency of the proposed RGWO in optimizing the milling process within different strategies. The results indicated that the RGWO outperforms the other solution methods in the literature as well as two novel meta-heuristic algorithms by obtaining better and feasible solutions for all cutting strategies.

     

A heuristic partitioning algorithm for a packaging problem

A heuristic algorithm for solving a problem of a minimum-cost packaging ofN items of the magnitudea _j intoM boxes of the capacityb _i with a costc _ij being assigned to the itemj packing into the boxi is presented. The principal idea of the algorithm consists in the preliminary partitioning of the problem into smaller subproblems and getting an approximate solution by solving these subproblems. A motivation of the heuristic and an application of the algorithm are given.     

An integrated approach to the design and operation for spare parts logistic systems

This paper attempts to solve a comprehensive design problem for a spare part logistic system. The design factors encompass logistic network design, part vendor selection, and transportation modes selection. Two approaches to solve the problem were proposed. In Approach 1, we simultaneously considered all the design factors and proposed two algorithms (SGA-1 and TGA-1). In Approach 2, the design problem was solved in two stages. Firstly, we aimed to find a near-optimal logistic network. Secondly, with the obtained logistic network, we proposed three algorithms (SGA-2, TGA-2, and NN-GA-Tabu) to find optimal combinations for part vendor and transportation modes selection. Numerical experiments indicate that Approach 2 outperforms Approach 1, and the NN-GA-Tabu outperforms all the other four algorithms. The proposed NN-GA-Tabu might also be a good solution architecture for solving other comprehensive space search problems.     

The continuous artificial bee colony algorithm for binary optimization

Artificial bee colony (ABC) algorithm, one of the swarm intelligence algorithms, has been proposed for continuous optimization, inspired intelligent behaviors of real honey bee colony. For the optimization problems having binary structured solution space, the basic ABC algorithm should be modified because its basic version is proposed for solving continuous optimization problems. In this study, an adapted version of ABC, ABC_bin for short, is proposed for binary optimization. In the proposed model for solving binary optimization problems, despite the fact that artificial agents in the algorithm works on the continuous solution space, the food source position obtained by the artificial agents is converted to binary values, before the objective function specific for the problem is evaluated. The accuracy and performance of the proposed approach have been examined on well-known 15 benchmark instances of uncapacitated facility location problem, and the results obtained by ABC_bin are compared with the results of continuous particle swarm optimization (CPSO), binary particle swarm optimization (BPSO), improved binary particle swarm optimization (IBPSO), binary artificial bee colony algorithm (binABC) and discrete artificial bee colony algorithm (DisABC). The performance of ABC_bin is also analyzed under the change of control parameter values. The experimental results and comparisons show that proposed ABC_bin is an alternative and simple binary optimization tool in terms of solution quality and robustness.     

约束可满足性中求解RB模型实例的算法综述

约束满足问题是人工智能领域中最基本的NP完全问题之一。多年来,随着约束满足问题的深入研究,国内外学者提出多种实例模型。其中,RB模型是一种能生成具有精确相变的增长域约束满足问题实例,其求解难度极具挑战性。为了寻找其求解的新型高效算法,促进约束可满足问题的RB模型求解算法领域的研究,首先从约束满足问题的模型发展、求解技术进行分析;其次,对各类求解RB模型实例算法进行梳理,将求解的算法文献划分为回溯启发式类、信息传播类和元启发式类相关改进算法,从算法原理、改进策略、收敛性和精确度等方面进行对比综述;最后给出求解RB模型实例算法的研究趋势和发展方向。     

Scheduling of multiple in-line steppers for semiconductor wafer fabs

A few prior studies noticed that an in-line stepper (a bottleneck machine in a semiconductor fab) may have a capacity loss while operated in a low-yield scenario. To alleviate such a capacity loss, some meta-heuristic algorithms for scheduling a single in-line stepper were proposed. Yet, in practice, there are multiple in-line steppers to be scheduled in a fab. This article aims to enhance prior algorithms so as to deal with the scheduling for multiple in-line steppers. Compared to prior studies, this research has to additionally consider how to appropriately allocate jobs to various machines. We enhance prior algorithms by developing a chromosome-decoding scheme which can yield a job-allocation decision for any given chromosome (or job sequence). Seven enhanced versions of meta-heuristic algorithms (genetic algorithm, Tabu, GA–Tabu, simulated annealing, M-MMAX, PACO and particle swarm optimisation) were then proposed and tested. Numerical experiments indicate that the GA–Tabu method outperforms the others. In addition, the lower the process yield, the better is the performance of the GA–Tabu algorithm.     

A new high performance approach: merging optimal multicast sessions for supporting multisource routing

Each single source multicast session (SSMS) transmits packets from a source node s _i to a group of destination nodes t _i , i=1,2,…,n. An SSMS’s path can be established with a routing algorithm, which constructs multicast path between source and destinations. Also, for each SSMS, the routing algorithm must be performed once. When the number of SSMS increases to N≥2, the routing algorithm must be separately performed N≥2 times because the number of source nodes increase to N≥2 (for each SSMS the routing algorithm must be performed once). This causes that time of computation and bandwidth consumption to grow. To remove this problem, in this paper, we will present a new approach for merging different SSMSs to make a new multicast session, which is performed only with one execution of a routing algorithm. The new approach, merging different sessions together, is based on the optimal resource allocation and Constraint Based Routing (CBR). We will show that as compared to other available routing algorithms, it improves time of computation and bandwidth consumption and increases data rate and network efficiency. The new approach uses CBR and merges more than one single source multicast session (SSMS) problem to one multisource multicast session (MSMS) problem. By solving one MSMS problem instead of solving more than one SSMS, we can obtain an optimal solution that is more efficient than optimal solutions of SSMS problems.