Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion

Recently, iterated greedy algorithms have been successfully applied to solve a variety of combinatorial optimization problems. This paper presents iterated greedy algorithms for solving the blocking flowshop scheduling problem (BFSP) with the makespan criterion. Main contributions of this paper can be summed up as follows. We propose a constructive heuristic to generate an initial solution. The constructive heuristic generates better results than those currently in the literature. We employ and adopt well-known speed-up methods from the literature for both insertion and swap neighborhood structures. In addition, an iteration jumping probability is proposed to change the neighborhood structure from insertion neighborhood to swap neighborhood. Generally speaking, the insertion neighborhood is much more effective than the swap neighborhood for the permutation flowshop scheduling problems. Instead of considering the use of these neighborhood structures in a framework of the variable neighborhood search algorithm, two powerful local search algorithms are designed in such a way that the search process is guided by an iteration jumping probability determining which neighborhood structure will be employed. By doing so, it is shown that some additional enhancements can be achieved by employing the swap neighborhood structure with a speed-up method without jeopardizing the effectiveness of the insertion neighborhood. We also show that the performance of the iterated greedy algorithm significantly depends on the speed-up method employed. The parameters of the proposed iterated greedy algorithms are tuned through a design of experiments on randomly generated benchmark instances. Extensive computational results on Taillard’s well-known benchmark suite show that the iterated greedy algorithms with speed-up methods are equivalent or superior to the best performing algorithms from the literature. Ultimately, 85 out of 120 problem instances are further improved with substantial margins.     

A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.     

An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem

In this work, we tackle the problem of scheduling a set of jobs on a set of unrelated parallel machines with minimising the total weighted completion times as performance criteria. The iterated greedy metaheuristic generates a sequence of solutions by iterating over a constructive heuristic using destruction and construction phases. In the last few years, iterated greedy has been employed to solve a considerable number of problems. This is because it is based on a very simple principle, it is easy to implement, and it often exhibits an excellent performance. Moreover, scalability for high-dimensional problems becomes an essential requirement for modern optimisation algorithms. This paper proposes an iterated greedy model for the above-mentioned scheduling problem to tackle large-size instances. The benefits of our proposal in comparison to existing metaheuristics proposed in the literature are experimentally shown.     

An AIS-based hybrid algorithm for static job shop scheduling problem

A static job shop scheduling problem (JSSP) is a class of JSSP which is a combinatorial optimization problem with the assumption of no disruptions and previously known knowledge about the jobs and machines. A new hybrid algorithm based on artificial immune systems (AIS) and particle swarm optimization (PSO) theory is proposed for this problem with the objective of makespan minimization. AIS is a metaheuristics inspired by the human immune system. Its two theories, namely, clonal selection and immune network theory, are integrated with PSO in this research. The clonal selection theory builds up the framework of the algorithm which consists of selection, cloning, hypermutation, memory cells extraction and receptor editing processes. Immune network theory increases the diversity of antibody set which represents the solution repertoire. To improve the antibody hypermutation process to accelerate the search procedure, a modified version of PSO is inserted. This proposed algorithm is tested on 25 benchmark problems of different sizes. The results demonstrate the effectiveness of the PSO algorithm and the specific memory cells extraction process which is one of the key features of AIS theory. By comparing with other popular approaches reported in existing literatures, this algorithm shows great competitiveness and potential, especially for small size problems in terms of computation time.     

An Effective PSO and AIS-Based Hybrid Intelligent Algorithm for Job-Shop Scheduling

The optimization of job-shop scheduling is very important because of its theoretical and practical significance. In this paper, a computationally effective algorithm of combining PSO with AIS for solving the minimum makespan problem of job-shop scheduling is proposed. In the particle swarm system, a novel concept for the distance and velocity of a particle is presented to pave the way for the job-shop scheduling problem. In the artificial immune system, the models of vaccination and receptor editing are designed to improve the immune performance. The proposed algorithm effectively exploits the capabilities of distributed and parallel computing of swarm intelligence approaches. The algorithm is examined by using a set of benchmark instances with various sizes and levels of hardness and is compared with other approaches reported in some existing literature works. The computational results validate the effectiveness of the proposed approach.     

An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem

Permutation flowshop scheduling problems (PFSPs) and, in particular, the variant with the objective of minimizing makespan have received an enormous attention in scheduling research and combinatorial optimization. As a result, the algorithmic approaches to this PFSP variant have reached extremely high performance. Currently, one of the most effective algorithm for this problem is a structurally rather simple iterated greedy algorithm. In this paper, we explore the possibility of re-optimizing partial solutions obtained after the solution destruction step of the iterated greedy algorithm. We show that with this extension, the performance of the state-of-the-art algorithm for the PFSP under makespan criterion can be significantly improved and we give experimental evidence that the local search on partial solutions is the key component for the high performance of the algorithm.     

基于公平性的OFDMA系统中自适应功率分配贪婪算法

功率分配是OFDMA系统资源调度中的一个重要研究问题。该文通过考虑功率分配中系统吞吐量与用户间公平性能平衡问题,提出了一种公平约束下的功率分配贪婪算法。将算法与经典算法比较,在使用户公平性大为提高的同时,使OFDM系统达到最大吞吐量。仿真结果表明,该算法的吞吐量逼近迭代注水功率分配算法。     

Metaheuristics for the single machine weighted quadratic tardiness scheduling problem

This paper considers the single machine scheduling problem with weighted quadratic tardiness costs. Three metaheuristics are presented, namely iterated local search, variable greedy and steady-state genetic algorithm procedures. These address a gap in the existing literature, which includes branch-and-bound algorithms (which can provide optimal solutions for small problems only) and dispatching rules (which are efficient and capable of providing adequate solutions for even quite large instances). A simple local search procedure which incorporates problem specific information is also proposed.The computational results show that the proposed metaheuristics clearly outperform the best of the existing procedures. Also, they provide an optimal solution for all (or nearly all, in the case of the variable greedy heuristic) the smaller size problems. The metaheuristics are quite close in what regards solution quality. Nevertheless, the iterated local search method provides the best solution, though at the expense of additional computational time. The exact opposite is true for the variable greedy procedure, while the genetic algorithm is a good all-around performer.     

Artificial immune systems for assembly sequence planning exploration

Assembly sequence planning (ASP) needs to take relevant constraint factors such as the geometric characteristics and tool factors into consideration so as to work out a particular assembly sequence. At last, a product will come into being through the assembly of each part according to the assembly sequence. A problem encountered in ASP is that a larger number of components will cause more constraints to assembly a product, thus increasing the complexity of assembly problem. Therefore, it has been an objective for researchers to look for suitable methods for the solution space of feasible solutions.Among them, traditional genetic algorithms (GAs) belong to a random searching method. When the constraints are complicated in ASP, GAs often come out with a large number of solutions not feasible. Consequently, previous research results have proposed some approaches such as Guided genetic algorithms (Guided-GAs) or memetic algorithms (MAs) to enhance the structure of GAs to cope with the complexity of constraints in ASP problems. In this study, artificial immune systems (AIS) were proposed to help solve the assembly sequence problem. In AIS algorithm, the antibody (Ab) in the immune system is simulated to encounter one or more unknown antigens (Ags). Moreover, the clonal selection concept is employed in the immune system in which a better antibody will be selected in each generation of revolution and different antibodies will be cloned to protect the infection of the original antigen. With this mechanism, the shortcoming such as the traditional GAs to converge in local optimal solution will be overcome. Practical examples have demonstrated that AIS can solve the ASP problem with complicated constraints. Compared with guided genetic algorithms and memetic algorithms, AIS can generate the same or better solutions in terms of quality and searching time.     

具有模糊处理时间的网格任务调度免疫算法

目前，网格计算作为一种新的计算范式正在兴起。任务调度是其中的一个重要研究领域。该文以AIS的克隆选择算法为基础，给出了基于人工免疫系统的网格任务调度算法。首先，对网格任务调度问题进行模糊化，并给出了形式化描述，随后用结构化的语言对算法进行了说明，最后通过仿真实验对算法的有效性以及算法参数对性能的影响进行了验证。     

An immunoglobulin-based artificial immune system for solving the hybrid flow shop problem

We consider the n-job, k-stage problem in a hybrid flow shop (HFS) with the objective of minimizing the maximum completion time, or makespan, which is an NP-hard problem. An immunoglobulin-based artificial immune system algorithm, called IAIS algorithm, is developed to search for the best sequence. IAIS, which is better fit the natural immune system, improves the existing AIS by the process before/after encounter with antigens. Before encounter with antigens, a new method of somatic recombination is presented; after encounter with antigens, an isotype switching is proposed. The isotype switching is a new approach in artificial immune system, and its purpose is to produce antibodies with the same protection but different function to defense the antigen. To verify IAIS, comparisons with the existing immune-based algorithms and other non-immune-based algorithms are made. Computational results show that IAIS is very competitive for the hybrid flow shop scheduling problem.     

An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem

This paper proposes a Tabu-mechanism improved iterated greedy (TMIIG) algorithm to solve the no-wait flowshop scheduling problem with a makespan criterion. The idea of seeking further improvement in the iterated greedy (IG) algorithm framework is based on the observation that the construction phase of the original IG algorithm may not achieve good performance in escaping from local minima when incorporating the insertion neighborhood search. To overcome this limitation, we have modified the IG algorithm by utilizing a Tabu-based reconstruction strategy to enhance its exploration ability. A powerful neighborhood search method that involves insert, swap, and double-insert moves is then applied to obtain better solutions from the reconstructed solution in the previous step. Empirical results on several benchmark problem instances and those generated randomly confirm the advantages of utilizing the new reconstruction scheme. In addition, our results also show that the proposed TMIIG algorithm is relatively more effective in minimizing the makespan than other existing well-performing heuristic algorithms.     

Optimal scheduling-based RFID reader-to-reader collision avoidance method using artificial immune system

In radio frequency identification (RFID) systems, communication signals from one desired reader is subject to interference from the other adjacent readers operating at the same time, so the reader-to-reader collision problem occurs. Many RFID reader collision avoidance methods have been developed, such as coverage-based methods, control mechanism-based methods and scheduling-based methods. In the scheduling-based methods, how to allocate frequency channels and time slots for the RFID reader network is emphasized. In this case, the RFID reader collision avoidance problem is transferred as an optimal scheduling problem, which can be solved by analytical methods and intelligent algorithms. Artificial Immune System (AIS) optimization is an emerging heuristic method derived from the human immune system. Due to its powerful global searching capability, AIS has been widely applied to scientific and engineering problems. This paper attempts to formulate the reader-to-reader collision problem (R2RCP) and its scheduling-based reader-to-reader collision avoidance model (R2RCAM), and proposes an improved AIS optimization for resource allocation (RA-AIS) in R2RCAM. Within the proposed RA-AIS optimization, the candidate antibody is constructed by using frequency channels and time slots, and in the mutation phase, the candidate antibody evolves dynamically according to its corresponding readers’ interfering power. The proposed RA-AIS optimization is examined on a series of numerical experiments to evaluate the effects of time slots, frequency channels, and transmitting power. Moreover, a group of comparative experiments are also arranged. The experimental results demonstrate that the proposed RA-AIS optimization is an effective method for R2RCAM, and performs better in searching the maximum interrogation area than other algorithms, such as random method (RM), genetic algorithm (GA), particle swarm optimization (PSO) and the canonical artificial immune system optimization (opt-aiNet).     

Intelligent multi-user detection using an artificial immune system

Artificial immune systems (AIS) are a kind of new computational intelligence methods which draw inspiration from the human immune system. In this study, we introduce an AIS-based optimization algorithm, called clonal selection algorithm, to solve the multi-user detection problem in code-division multiple-access communications system based on the maximum-likelihood decision rule. Through proportional cloning, hypermutation, clonal selection and clonal death, the new method performs a greedy search which reproduces individuals and selects their improved maturated progenies after the affinity maturation process. Theoretical analysis indicates that the clonal selection algorithm is suitable for solving the multi-user detection problem. Computer simulations show that the proposed approach outperforms some other approaches including two genetic algorithm-based detectors and the matched filters detector, and has the ability to find the most likely combinations.     

Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates

In this paper, we consider an identical parallel machine scheduling problem with sequence-dependent setup times and job release dates. An improved iterated greedy heuristic with a sinking temperature is presented to minimize the maximum lateness. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem data set. The experimental results show that the proposed heuristic outperforms the basic iterated greedy heuristic and the state-of-art algorithms on the same benchmark problem data set. It is believed that this improved approach will also be helpful for other applications.     

A hybrid algorithmic model for the minimum weight dominating set problem

Iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where—given a vertex-weighted graph—the goal is to identify a subset of the graphs’ vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches.     

An artificial immune system for solving production scheduling problems: a review

This article reviews the production scheduling problems focusing on those related to flexible job-shop scheduling. Job-shop and flexible job-shop scheduling problems are one of the most frequently encountered and hardest to optimize. This article begins with a review of the job-shop and flexible job-shop scheduling problem, and follow by the literature on artificial immune systems (AIS) and suggests ways them in solving job-shop and flexible job-shop scheduling problems. For the purposes of this study, AIS is defined as a computational system based on metaphors borrowed from the biological immune system. This article also, summarizes the direction of current research and suggests areas that might most profitably be given further scholarly attention.     

基于任务分配与调度的GSAT算法求解3-SAT问题

基于不同分配策略的云计算任务调度以及任务分配与调度的主要目的,提出了一种新的算法—求解3-SAT问题的基于任务分配与调度的GSAT算法。该算法将3-SAT问题中的每一个变量形成一个任务,在GSAT算法的基础上,引入任务分配与调度指导贪心搜索;同时,在保留原有贪心搜索的前提下,根据任务分配与调度的思想和3-SAT问题的特点,设计了两种新的策略—分配策略和调度策略共同完成整个贪心搜索过程。以标准的SATLAB库中变量个数从 20～250的3 700个不同规模的标准Uniform Random 3-SAT 问题对新的算法的性能进行了合理的测试,并与高效和普通性能改进的GSAT算法的结果作了比较,结果表明,该算法具有更高的成功率和更少的翻转次数。     

A discrete differential evolution algorithm for the permutation flowshop scheduling problem

Very recently, Pan et al. [Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO07, pp. 126–33] presented a new and novel discrete differential evolution algorithm for the permutation flowshop scheduling problem with the makespan criterion. On the other hand, the iterated greedy algorithm is proposed by [Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033–49] for the permutation flowshop scheduling problem with the makespan criterion. However, both algorithms are not applied to the permutation flowshop scheduling problem with the total flowtime criterion. Based on their excellent performance with the makespan criterion, we extend both algorithms in this paper to the total flowtime objective. Furthermore, we propose a new and novel referenced local search procedure hybridized with both algorithms to further improve the solution quality. The referenced local search exploits the space based on reference positions taken from a reference solution in the hope of finding better positions for jobs when performing insertion operation. Computational results show that both algorithms with the referenced local search are either better or highly competitive to all the existing approaches in the literature for both objectives of makespan and total flowtime. Especially for the total flowtime criterion, their performance is superior to the particle swarm optimization algorithms proposed by [Tasgetiren, M. F., Liang, Y. -C., Sevkli, M., Gencyilmaz, G. (2007). Particle swarm optimization algorithm for makespan and total flowtime minimization in permutation flowshop sequencing problem. European Journal of Operational Research, 177(3), 1930–47] and [Jarboui, B., Ibrahim, S., Siarry, P., Rebai, A. (2007). A combinatorial particle swarm optimisation for solving permutation flowshop problems. Computers & Industrial Engineering, doi:10.1016/j.cie.2007.09.006]. Ultimately, for Taillard’s benchmark suite, four best known solutions for the makespan criterion as well as 40 out of the 90 best known solutions for the total flowtime criterion are further improved by either one of the algorithms presented in this paper.     

A noniterative greedy algorithm for multiframe point correspondence

This work presents a framework for finding point correspondences in monocular image sequences over multiple frames. The general problem of multiframe point correspondence is NP-hard for three or more frames. A polynomial time algorithm for a restriction of this problem is presented and is used as the basis of the proposed greedy algorithm for the general problem. The greedy nature of the proposed algorithm allows it to be used in real-time systems for tracking and surveillance, etc. In addition, the proposed algorithm deals with the problems of occlusion, missed detections, and false positives by using a single noniterative greedy optimization scheme and, hence, reduces the complexity of the overall algorithm as compared to most existing approaches where multiple heuristics are used for the same purpose. While most greedy algorithms for point tracking do not allow the entry and exit of the points from the scene, this is not a limitation for the proposed algorithm. Experiments with real and synthetic data over a wide range of scenarios and system parameters are presented to validate the claims about the performance of the proposed algorithm.