Abstract
Hierarchically coupled constraint optimization (HCCO) problems are omnipresent, both in theoretical problems and in real-life scenarios; however, there is no clear definition to identify these problems. Numerous techniques have been developed for some typical HCCO problems, such as assembly job-shop scheduling problems (AJSSPs); however, these techniques are not universally applicable to all HCCO problems. In this paper, an abstract definition and common principles amongst different HCCO problems are first established. Next, based on the definitions and principles, a new optimization algorithm based on evolutionary computation is developed for HCCO. The new optimization algorithm has three key new features: a new initial solution generator, a level barrier-based crossover operator, and a level barrier-based mutation operator. In the initial solution generator, a partial solution is created in the first step that satisfies the lowest level hierarchically coupled constraint (HCC) and each consecutive step afterwards adds on to the partial solution to satisfy the next higher level of HCC. In the level barrier-based operators, the operations are only performed between genes satisfying the same level of HCCs to ensure feasibility of the new solutions. The developed optimization algorithm is used to solve a variety of AJSSPs and the results obtained using the proposed algorithm are compared to other methods used to solve AJSSPs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Abbreviations
- \({{\varvec{a}}}_{{\varvec{n}}}\) :
-
\(n{\hbox {th}}\) independent variable
- \({{\varvec{x}}}({{\varvec{a}}}_{{\varvec{i}}})\) :
-
The frequency of occurrence of the variable \(x(a_i)\)
- \({{\varvec{b}}}_{{{\varvec{m}}}_{{\varvec{1}}}}^{\left( \mathbf{1} \right) }\) :
-
\(m_1\)-dependent variable belonging to the \(1{\mathrm{st}}\) level
- \({{\varvec{C}}}_{{{\varvec{a}}}_\mathbf{1}}\) :
-
Constraint on the independent variable \(a_1\)
- \({{\varvec{C}}}_{{{\varvec{b}}}_\mathbf{1}}\) :
-
Constraint on the dependent \(b_1\)
- \({{\varvec{l}}}_{{{\varvec{a}}}_{{\varvec{i}}}}\) :
-
Location of variable \(a_i\) in the chromosome
- \({{\varvec{l}}}_{{{\varvec{b}}}_\mathbf{1}^{\left( \mathbf{1} \right) }}\) :
-
Location of variable \(b_1^{\left( 1 \right) }\) in the chromosome
- \({{\varvec{G}}}_{{{\varvec{j}}}_\mathbf{1}}^{\left( \mathbf{0} \right) }\) :
-
\(j_1 \; 0{\mathrm{th}}\)-level gene
- \({{\varvec{w}}}_{{{\varvec{j}}}_\mathbf{1}, {{\varvec{i}}}}^{\left( \mathbf{0} \right) }\) :
-
Weight values of the independent variable \(a_i\) for gene \(G_{j_1 }^{\left( 0 \right) }\)
- \({{\varvec{w}}}_{{{\varvec{j}}}_\mathbf{2}, {{\varvec{j}}}_\mathbf{1}}^{\left( \mathbf{1} \right) }\) :
-
Weight values of the \(1{\mathrm{st}}\)-level dependent variable \(b_{j_1 }^{\left( 1 \right) }\) for gene \(G_{j_1 }^{\left( 1 \right) }\)
- \({{\varvec{w}}}_{{\varvec{x}}}\) :
-
Crossover weight values
- \({{\varvec{w}}}_{{\varvec{x}}} \left( {{{\varvec{r}}}_\mathbf{0} } \right) \) :
-
Crossover weight value for the \(r_0{\hbox {th}}\) level
- \({{\varvec{w}}}_{{\varvec{m}}}\) :
-
Mutation-level weight values
- \({{\varvec{w}}}_{{\varvec{m}}} \left( {{{\varvec{r}}}_\mathbf{0}} \right) \) :
-
Mutation weight value for the \(r_0{\hbox {th}}\) level
- \({{\varvec{x}}}_{{\varvec{p}}}\) :
-
Random integer between 1 and \(m_{r_0}\)
- \({{\varvec{CM}}}^{\left( \mathbf{0} \right) }\) :
-
Mutation candidates for the \(0{\mathrm{th}}\) level
- \({{\varvec{CM}}}\) :
-
Mutation candidates for all levels
- \({{\varvec{\hbox {CG}}}}_{{{\varvec{b}}}_{{{\varvec{m}}}_{\left( {{{\varvec{r}}}_\mathbf{0} +\mathbf{1}} \right) } }^{\left( {{{\varvec{r}}}_\mathbf{0} +\mathbf{1}} \right) } }^{\left( {{{\varvec{r}}}_\mathbf{0}} \right) }\) :
-
A vector containing gene groups belonging to the \(r_{o}\) level that constrains the \(b_{m_{\left( {r_0 +1} \right) } }^{\left( {r_0 +1} \right) }\) dependent variable and has the length c
- \({{\varvec{P}}}_{{{\varvec{rm}}}}\) :
-
Mutation probability (between 0 and 1)
- \({{\varvec{P}}}\) :
-
Random integer between 1 and \(m_{\left( {r_0 +1} \right) }\)
- \({{\varvec{Q}}}\) :
-
Random integer between 1 and number of genes in c
- \({{\varvec{R}}}\) :
-
Random integer between 2 and the number of genes in \({\hbox {CG}}_{b_{m_{\left( P \right) } }^{\left( {r_0 +1} \right) } }^{\left( {r_0 } \right) } \left( Q \right) -R\)
- \({{\varvec{n}}}\) :
-
Number of genes in \({\hbox {CG}}_{b_{m_{\left( P \right) } }^{\left( {r_0 -1} \right) } }^{\left( {r_0 } \right) } \left( Q \right) -R\)
References
Coello, C. A. C. (2002). Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art. Computer Methods in Applied Mechanics and Engineering, 191(11), 1245–1287.
Watanabe, K., & Hashem, M. M. A. (2004). Evolutionary optimization of constrained problems. In K. Watanabe & M. M. A. Hashem (Eds.), Evolutionary computations (pp. 53–64). Berlin: Springer.
Ali, M. M., Golalikhani, M., & Zhuang, J. (2014). A computational study on different penalty approaches for solving constrained global optimization problems with the electromagnetism-like method. Optimization, 63(3), 403–419.
Snyman, J. A., Stander, N., & Roux, W. J. (1994). A dynamic penalty function method for the solution of structural optimization problems. Applied Mathematical Modelling, 18(8), 453–460.
Koziel, S., & Michalewicz, Z. (1999). Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization. Evolutionary Computation, 7(1), 19–44.
Monson, C. K., & Seppi, K. D. (2005). Linear equality constraints and homomorphous mappings in PSO. In 2005 IEEE congress on evolutionary computation (Vol. 1, pp. 73–80).
Michalewicz, Z., & Janikow, C. Z. (1996). GENOCOP: A genetic algorithm for numerical optimization problems with linear constraints. Communications of the ACM, 39(12es), 175.
Chootinan, P., & Chen, A. (2006). Constraint handling in genetic algorithms using a gradient-based repair method. Computers & Operations Research, 33(8), 2263–2281.
Pal, K., Saha, C., Das, S., & Coello, C. A. C. (2013). Dynamic constrained optimization with offspring repair based gravitational search algorithm. In 2013 IEEE congress on evolutionary computation (pp. 2414–2421).
Michalewicz, Z., & Nazhiyath, G. (1995). Genocop III: A co-evolutionary algorithm for numerical optimization problems with nonlinear constraints. In IEEE international conference on evolutionary computation, 1995 (Vol. 2, pp. 647–651).
Ameca-Alducin, M. Y., Mezura-Montes, E., & Cruz-Ramírez, N. (2015). A repair method for differential evolution with combined variants to solve dynamic constrained optimization problems. In Proceedings of the 2015 annual conference on genetic and evolutionary computation (pp. 241–248).
Deb, K. (2000). An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 186(2), 311–338.
Ma, H., & Simon, D. (2011). Blended biogeography-based optimization for constrained optimization. Engineering Applications of Artificial Intelligence, 24(3), 517–525.
Chen, H., Zhou, Y., Guo, P., Ouyang, X., He, S., & Zheng, H. (2013). A hybrid invasive weed optimization with feasibility-based rule for constrained optimization problem. Przegląd Elektrotechniczny, 89(4), 160–167.
Zhou, Y., Zhou, G., & Zhang, J. (2013). A hybrid glowworm swarm optimization algorithm for constrained engineering design problems. Applied Mathematics & Information Sciences, 7(1), 379–388.
Mohamed, A. W., & Sabry, H. Z. (2012). Constrained optimization based on modified differential evolution algorithm. Information Sciences, 194, 171–208.
Fattahi, P., Hosseini, S. M. H., Jolai, F., & Tavakkoli-Moghaddam, R. (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations. Applied Mathematical Modelling, 38(1), 119–134.
Komaki, G. M., & Kayvanfar, V. (2015). Grey Wolf optimizer algorithm for the two-stage assembly flow shop scheduling problem with release time. Journal of Computational Science, 8, 109–120.
Yan, H. S., Wan, X. Q., & Xiong, F. L. (2014). A hybrid electromagnetism-like algorithm for two-stage assembly flow shop scheduling problem. International Journal of Production Research, 52(19), 5626–5639.
Komaki, G. M., Teymourian, E., & Kayvanfar, V. (2016). Minimising makespan in the two-stage assembly hybrid flow shop scheduling problem using artificial immune systems. International Journal of Production Research, 54(4), 963–983.
Wong, T. C., & Ngan, S. C. (2013). A comparison of hybrid genetic algorithm and hybrid particle swarm optimization to minimize makespan for assembly job shop. Applied Soft Computing, 13(3), 1391–1399.
Natarajan, K., Mohanasundaram, K. M., Babu, B. S., Suresh, S., Raj, K. A. A. D., & Rajendran, C. (2007). Performance evaluation of priority dispatching rules in multi-level assembly job shops with jobs having weights for flowtime and tardiness. The International Journal of Advanced Manufacturing Technology, 31(7), 751–761.
Paul, M., Sridharan, R., & Ramanan, T. R. (2015). An investigation of order review/release policies and dispatching rules for assembly job shops with multi objective criteria. Procedia-Social and Behavioral Sciences, 189, 376–384.
Chan, F. T. S., Wong, T. C., & Chan, L. Y. (2008). Lot streaming for product assembly in job shop environment. Robotics and Computer-Integrated Manufacturing, 24(3), 321–331.
Guo, Z. X., Wong, W. K., Leung, S. Y. S., Fan, J. T., & Chan, S. F. (2006). Mathematical model and genetic optimization for the job shop scheduling problem in a mixed-and multi-product assembly environment: A case study based on the apparel industry. Computers & Industrial Engineering, 50(3), 202–219.
Thiagarajan, S., & Rajendran, C. (2003). Scheduling in dynamic assembly job-shops with jobs having different holding and tardiness costs. International Journal of Production Research, 41(18), 4453–4486.
Fuji, W., Jianwei, M., Di, S., Wei, L., & Xiaohong, L. (2012). Research on repair operators in the whole space search genetic algorithm of assembly job shop scheduling problem. In 2012 7th IEEE conference on industrial electronics and applications (ICIEA) (pp. 1922–1927).
Liao, C. J., Lee, C. H., & Lee, H. C. (2015). An efficient heuristic for a two-stage assembly scheduling problem with batch setup times to minimize makespan. Computers & Industrial Engineering, 88, 317–325.
Seidgar, H., Kiani, M., Abedi, M., & Fazlollahtabar, H. (2014). An efficient imperialist competitive algorithm for scheduling in the two-stage assembly flow shop problem. International Journal of Production Research, 52(4), 1240–1256.
Dileeplal, J., & Narayanan, K. P. (2012). Multi-objective assembly job shop scheduling using genetic algorithm and tabu search. Doctoral dissertation, Cochin University of Science and Technology.
Bierwirth, C. (1995). A generalized permutation approach to job shop scheduling with genetic algorithms. Operations Research Spektrum, 17(2–3), 87–92.
Beasley, D., Martin, R. R., & Bull, D. R. (1993). An overview of genetic algorithms: Part 1. Fundamentals. University Computing, 15, 58–58.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zou, P., Rajora, M. & Liang, S.Y. A new algorithm based on evolutionary computation for hierarchically coupled constraint optimization: methodology and application to assembly job-shop scheduling. J Sched 21, 545–563 (2018). https://doi.org/10.1007/s10951-018-0572-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-018-0572-2