A hybrid genetic-immune algorithm with improved lifespan and elite antigen for flow-shop scheduling problems. (English) Zbl 1356.90053
Summary: In this paper, a hybrid genetic-immune algorithm (HGIA) is proposed to reduce the premature convergence problem in a genetic algorithm (GA) in solving permutation flow-shop scheduling problems. A co-evolutionary strategy is proposed for efficient combination of GA and an artificial immune system (AIS). First, the GA is adopted to generate antigens with better fitness, and then the population in the last generation is transformed into antibodies in AIS. A new formula for calculating the lifespan of each antibody is employed during the evolution processes. In addition, a new mechanism including T-cell and B-cell generation procedures is applied to produce different types of antibodies which will be merged together. The antibodies with longer lifespan will survive and enter the next generation. This co-evolutionary strategy is very effective since chromosomes and antibodies will be transformed and evolved dynamically. The intensive experimental results show the effectiveness of the HGIA approach. The hybrid algorithm can be further extended to solve different combinatorial problems.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
flow-shop scheduling problems; genetic algorithm; artificial immune system; co-evolutional process; early convergenceReferences:
| [1] | DOI: 10.1080/00207540500337585 · doi:10.1080/00207540500337585 |
| [2] | Baker K, Introduction to sequencing and scheduling (1974) |
| [3] | DOI: 10.1016/j.eswa.2005.04.033 · doi:10.1016/j.eswa.2005.04.033 |
| [4] | DOI: 10.1016/j.ijpe.2005.11.003 · doi:10.1016/j.ijpe.2005.11.003 |
| [5] | DOI: 10.1016/j.amc.2008.05.027 · Zbl 1152.90432 · doi:10.1016/j.amc.2008.05.027 |
| [6] | DOI: 10.1016/j.apm.2008.01.006 · Zbl 1167.90503 · doi:10.1016/j.apm.2008.01.006 |
| [7] | DOI: 10.1016/j.eswa.2009.07.066 · doi:10.1016/j.eswa.2009.07.066 |
| [8] | DOI: 10.1016/0360-8352(96)00042-3 · doi:10.1016/0360-8352(96)00042-3 |
| [9] | DOI: 10.1109/20.717694 · doi:10.1109/20.717694 |
| [10] | DOI: 10.1080/03052150410001704845 · doi:10.1080/03052150410001704845 |
| [11] | DOI: 10.1057/palgrave.jors.2601784 · Zbl 1088.90022 · doi:10.1057/palgrave.jors.2601784 |
| [12] | Garey MR, Computers and intractability: a guide to the theory of NP-completeness (1979) · Zbl 0411.68039 |
| [13] | Goldberg DE, Genetic algorithms in search, optimization and machine learning (1989) · Zbl 0721.68056 |
| [14] | DOI: 10.1080/0020754050056417 · Zbl 1068.90059 · doi:10.1080/0020754050056417 |
| [15] | DOI: 10.1109/TEVC.2003.810752 · doi:10.1109/TEVC.2003.810752 |
| [16] | DOI: 10.1016/S0305-0548(03)00016-9 · Zbl 1046.90028 · doi:10.1016/S0305-0548(03)00016-9 |
| [17] | DOI: 10.1137/0202009 · Zbl 0259.90031 · doi:10.1137/0202009 |
| [18] | DOI: 10.1016/j.amc.2005.07.042 · Zbl 1137.90503 · doi:10.1016/j.amc.2005.07.042 |
| [19] | DOI: 10.1080/00207540701523041 · Zbl 1152.90462 · doi:10.1080/00207540701523041 |
| [20] | DOI: 10.1016/0305-0548(93)E0014-K · Zbl 0815.90097 · doi:10.1016/0305-0548(93)E0014-K |
| [21] | DOI: 10.1162/evco.1998.6.1.45 · doi:10.1162/evco.1998.6.1.45 |
| [22] | DOI: 10.1016/j.ejor.2004.04.017 · Zbl 1066.90038 · doi:10.1016/j.ejor.2004.04.017 |
| [23] | DOI: 10.1016/j.amc.2007.04.038 · Zbl 1193.90114 · doi:10.1016/j.amc.2007.04.038 |
| [24] | DOI: 10.1080/00207540801910429 · Zbl 1198.90158 · doi:10.1080/00207540801910429 |
| [25] | DOI: 10.1080/00207540802400636 · Zbl 1198.90218 · doi:10.1080/00207540802400636 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
