Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Native metaheuristics for non-permutation flowshop scheduling

  • Published:
Journal of Intelligent Manufacturing Aims and scope Submit manuscript

Abstract

The most general flowshop scheduling problem is also addressed in the literature as non-permutation flowshop (NPFS). Current processors are able to cope with the \((n!)^{m}\) combinatorial complexity of NPFS scheduling by metaheuristics. After briefly discussing the requirements for a manufacturing layout to be designed and modeled as non-permutation flowshop, a disjunctive graph (digraph) approach is used to build native solutions. The implementation of an Ant Colony Optimization (ACO) algorithm has been described in detail; it has been shown how the biologically inspired mechanisms produce eligible schedules, as opposed to most metaheuristics approaches, which improve permutation solutions. ACO algorithms are an example of native non-permutation (NNP) solutions of the flowshop scheduling problem, opening a new perspective on building purely native approaches. The proposed NNP-ACO has been assessed over existing native approaches improving most makespan upper bounds of the benchmark problems from Demirkol et al. (1998).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  • Arnaout, J.-P., Musa, R., & Rabadi, G. (2012). A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines–part II: Enhancements and experimentations. Journal of Intelligent Manufacturing. doi:10.1007/s10845-012-0672-3.

  • Blum, C., & Sampels, M. (2004). An ant colony optimization algorithm for shop scheduling problem. Journal of Mathematical Modelling and Algorithms, 3, 285–308.

    Article  Google Scholar 

  • Bonabeau, E., Dorigo, M., & Theraulaz, G. (2000). Inspiration for optimization from social insect behaviour. Nature, 406, 39–42.

    Article  Google Scholar 

  • Brucker, P., Heitmann, S., & Hurink, J. (2003). Flow-shop problems with intermediate buffers. OR Spectrum, 25, 549–574.

    Article  Google Scholar 

  • Demirkol, E., Mehta, S., & Uzsoy, R. (1998). Benchmarks for shop scheduling problems. European Journal of Operational Research, 109, 137–141.

    Article  Google Scholar 

  • Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1, 53–66.

    Article  Google Scholar 

  • Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129.

    Article  Google Scholar 

  • Giffler, D., & Thompson, G. L. (1960). Algorithms for solving production scheduling problems. Operations Research, 8, 487–503.

    Article  Google Scholar 

  • Jain, A. S., & Meeran, S. (2002). A multi-level hybrid framework applied to the general flow-shop scheduling problem. Computers & Operations Research, 29, 1873–1901.

    Article  Google Scholar 

  • Johnson, S. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61.

    Article  Google Scholar 

  • Kumar, R., Tiwari, M. K., & Shankar, R. (2003). Scheduling of flexible manufacturing system: An ant colony optimization approach. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 217, 1443–1453.

    Article  Google Scholar 

  • Liao, C. J., Liao, L. M., & Tseng, C. T. (2006). A performance evaluation of permutation vs. non-permutation schedules in a flowshop. International Journal of Production Research, 44, 4297–4309.

    Article  Google Scholar 

  • Lin, S.-W., & Ying, K.-C. (2009). Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems. International Journal of Production Research, 47(5), 1411–1424. doi:10.1080/00207540701484939.

    Article  Google Scholar 

  • Mirabi, M., Fatemi Ghomi, S. M. T., & Jolai, F. (2011). A two-stage hybrid flowshop scheduling problem in machine breakdown condition. Journal of Intelligent Manufacturing. doi:10.1007/s10845-011-0553-1.

  • Nawaz, M., & Enscore, E. E, Jr. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA, The International Journal of Management Science, 11(1), 91–95.

    Article  Google Scholar 

  • Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job-shop problem. Management Science, 42(6), 797–813.

    Article  Google Scholar 

  • Pinedo, M. (1995). Scheduling: theory, algorithms and system. New Jersey: Prentice-Hall.

    Google Scholar 

  • Potts, C. N., Shmoys, D. B., & Williamson, D. P. (1991). Permutation vs. non-permutation flow shop schedules. Operations Research Letters, 10, 281–284.

    Article  Google Scholar 

  • Pugazhendhi, S., Thiagarajan, S., Rajendran, C., & Anantharaman, N. (2004). Generating non-permutation schedules in flowline-based manufacturing systems with sequence-dependent setup times of jobs: A heuristic approach. The International Journal of Advanced Manufacturing Technology, 23, 64–78.

    Google Scholar 

  • Pugazhendhi, S., Thiagarajan, S., Rajendran, C., & Anantharaman, N. (2002). Performance enhancement by using non-permutation schedules in flowline-based manufacturing systems. Computers and Industrial Engineering, 44(1), 133–157.

    Google Scholar 

  • Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155, 426–438.

    Article  Google Scholar 

  • Rossi, A., & Dini, G. (2007). Flexible job-shop scheduling with routing flexibility and separable setup time using ant colony optimisation method. Robotics and Computer Integrated Manufacturing, 23, 503–516.

    Google Scholar 

  • Rossi, A., & Lanzetta, M. (2013). Scheduling flow lines with buffers by ant colony digrap. Expert Systems with Applications. doi:10.1016/j.eswa.2012.12.041.

  • Rossi, A., Puppato, A., & Lanzetta, M. (2013). Heuristics for scheduling a two-stage hybrid flow shop with parallel batching machines: An application on hospital sterilization plant. International Journal of Production Research. doi:10.1080/00207543.2012.737942.

  • Sadjadi, S. J., Bouquard, J. L., & Ziaee, M. (2008). An ant colony algorithm for the flowshop scheduling problem. Journal of Applied Sciences, 8(21), 3938–44. ISSN:1812–5654, doi:10.3923/jas.2008.3938.3944.

    Google Scholar 

  • Stuetzle, T. (1998). An ant approach to the flow shop problem. Proceedings of the sixth European congress on intelligent techniques and soft computing (EUFIT’98), Verlag Mainz, Wissenschaftsverlag, Aachen, Germany, Vol. 3, pp. 1560–1564.

  • Stuetzle, T., & Hoos, H. H. (2000). Max-min ant system. Future Generation Computing Systems, 16(9), 889–914.

    Article  Google Scholar 

  • Tandon, M., Cummings, P. T., & LeVan, M. D. (1991). Flowshop sequencing with non-permutation schedules. Computers and Industrial Engineering, 15(8), 601–607.

    Google Scholar 

  • Tavares Neto, R. R., & Godinho Filho, M. (2013). Literature review regarding ant colony optimization applied to scheduling problems: Guidelines for implementation and directions for future research. Engineering Applications of Artificial Intelligence, 26, 150–161.

    Article  Google Scholar 

  • Vijay chakaravarthy, G., Marimuthu, S., & Naveen Sait, A. (2011). Performance evaluation of proposed differential evolution and particle swarm optimization algorithms for scheduling m-machine flow shops with lot streaming. Journal of Intelligent Manufacturing. doi:10.1007/s10845-011-0552-2.

  • Werner, F., & Winkler, A. (1995). Insertion techniques for the heuristic solution of the job-shop problem. Discrete Applied Mathematics, 58(2), 191–211.

    Article  Google Scholar 

  • Yagmahan, B., & Yenisey, M. M. (2010). A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications, 37, 1361–1368.

    Google Scholar 

  • Ying, K.-C., & Lin, S.-W. (2007). Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems. International Journal of Advanced Manufacturing Technology, 33, 793–802.

    Article  Google Scholar 

  • Ying, K.-C., Gupta, J. N. D., Lin, S.-W., & Lee, Z.-J. (2010). Permutation and non-permutation schedules for the flowline manufacturing cell with sequence dependent family setups. International Journal of Production Research, 48(8), 2169–2184.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Civil and Industrial Engineering, University of Pisa, Pisa, Italy

    Andrea Rossi & Michele Lanzetta

Authors
  1. Andrea Rossi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michele Lanzetta
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michele Lanzetta.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (txt 158 KB)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rossi, A., Lanzetta, M. Native metaheuristics for non-permutation flowshop scheduling. J Intell Manuf 25, 1221–1233 (2014). https://doi.org/10.1007/s10845-012-0724-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10845-012-0724-8

Keywords

Search

Navigation