IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v112y2008i2p742-755.html
   My bibliography  Save this article

Development of new features of ant colony optimization for flowshop scheduling

Author

Listed:
  • Lin, B.M.T.
  • Lu, C.Y.
  • Shyu, S.J.
  • Tsai, C.Y.

Abstract

Ant colony optimization (ACO) is a meta-heuristic based on the indirect communication of a colony of artificial ants mediated by pheromone trails with the collaboration and knowledge-sharing mechanism during their food-seeking process. In this study, we introduce two new features that are inspired from real ant behavior to develop a new ACO algorithm to produce better solutions. The proposed ACO algorithm is applied to two NP-hard flowshop scheduling problems. The first problem is to minimize the total completion time and the second is to minimize a combination of makespan and total completion time. Numerical results indicate that the proposed new features of ACO are very effective and the synergy of combining all the new features for the proposed ACO algorithm can solve the two problems to a certain scale by producing schedules of better quality.

Suggested Citation

  • Lin, B.M.T. & Lu, C.Y. & Shyu, S.J. & Tsai, C.Y., 2008. "Development of new features of ant colony optimization for flowshop scheduling," International Journal of Production Economics, Elsevier, vol. 112(2), pages 742-755, April.
    • Handle: RePEc:eee:proeco:v:112:y:2008:i:2:p:742-755
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925-5273(07)00243-5
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ferretti, Ivan & Zanoni, Simone & Zavanella, Lucio, 2006. "Production-inventory scheduling using Ant System metaheuristic," International Journal of Production Economics, Elsevier, vol. 104(2), pages 317-326, December.
    2. Rajendran, Chandrasekharan, 1993. "Heuristic algorithm for scheduling in a flowshop to minimize total flowtime," International Journal of Production Economics, Elsevier, vol. 29(1), pages 65-73, February.
    3. Rajendran, Chandrasekharan & Ziegler, Hans, 2004. "Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs," European Journal of Operational Research, Elsevier, vol. 155(2), pages 426-438, June.
    4. Shyong Shyu & Peng-Yeng Yin & Bertrand Lin, 2004. "An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem," Annals of Operations Research, Springer, vol. 131(1), pages 283-304, October.
    5. Fred Glover, 1990. "Tabu Search: A Tutorial," Interfaces, INFORMS, vol. 20(4), pages 74-94, August.
    6. Nawaz, Muhammad & Enscore Jr, E Emory & Ham, Inyong, 1983. "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega, Elsevier, vol. 11(1), pages 91-95.
    7. Della Croce, F. & Narayan, V. & Tadei, R., 1996. "The two-machine total completion time flow shop problem," European Journal of Operational Research, Elsevier, vol. 90(2), pages 227-237, April.
    8. L M Gambardella & É D Taillard & M Dorigo, 1999. "Ant colonies for the quadratic assignment problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(2), pages 167-176, February.
    9. T'kindt, Vincent & Monmarche, Nicolas & Tercinet, Fabrice & Laugt, Daniel, 2002. "An Ant Colony Optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 142(2), pages 250-257, October.
    10. Nagar, Amit & Haddock, Jorge & Heragu, Sunderesh, 1995. "Multiple and bicriteria scheduling: A literature survey," European Journal of Operational Research, Elsevier, vol. 81(1), pages 88-104, February.
    11. Gajpal, Yuvraj & Rajendran, Chandrasekharan, 2006. "An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops," International Journal of Production Economics, Elsevier, vol. 101(2), pages 259-272, June.
    12. R. A. Dudek & S. S. Panwalkar & M. L. Smith, 1992. "The Lessons of Flowshop Scheduling Research," Operations Research, INFORMS, vol. 40(1), pages 7-13, February.
    13. Della Croce, F. & Ghirardi, M. & Tadei, R., 2002. "An improved branch-and-bound algorithm for the two machine total completion time flow shop problem," European Journal of Operational Research, Elsevier, vol. 139(2), pages 293-301, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yenisey, Mehmet Mutlu & Yagmahan, Betul, 2014. "Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends," Omega, Elsevier, vol. 45(C), pages 119-135.
    2. Tseng, Lin-Yu & Lin, Ya-Tai, 2010. "A hybrid genetic algorithm for no-wait flowshop scheduling problem," International Journal of Production Economics, Elsevier, vol. 128(1), pages 144-152, November.
    3. Wang, Sheng-yao & Wang, Ling & Liu, Min & Xu, Ye, 2013. "An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 145(1), pages 387-396.
    4. Sabuncuoglu, Ihsan & Erel, Erdal & Alp, Arda, 2009. "Ant colony optimization for the single model U-type assembly line balancing problem," International Journal of Production Economics, Elsevier, vol. 120(2), pages 287-300, August.
    5. Huang, Rong-Hwa, 2010. "Multi-objective job-shop scheduling with lot-splitting production," International Journal of Production Economics, Elsevier, vol. 124(1), pages 206-213, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sündüz Dağ, 2013. "An Application On Flowshop Scheduling," Alphanumeric Journal, Bahadir Fatih Yildirim, vol. 1(1), pages 47-56, December.
    2. Li, Xiaoping & Wang, Qian & Wu, Cheng, 2009. "Efficient composite heuristics for total flowtime minimization in permutation flow shops," Omega, Elsevier, vol. 37(1), pages 155-164, February.
    3. Framinan, Jose M. & Leisten, Rainer & Ruiz-Usano, Rafael, 2002. "Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation," European Journal of Operational Research, Elsevier, vol. 141(3), pages 559-569, September.
    4. Gajpal, Yuvraj & Rajendran, Chandrasekharan, 2006. "An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops," International Journal of Production Economics, Elsevier, vol. 101(2), pages 259-272, June.
    5. Bo Liu & Ling Wang & Ying Liu & Shouyang Wang, 2011. "A unified framework for population-based metaheuristics," Annals of Operations Research, Springer, vol. 186(1), pages 231-262, June.
    6. Varadharajan, T.K. & Rajendran, Chandrasekharan, 2005. "A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs," European Journal of Operational Research, Elsevier, vol. 167(3), pages 772-795, December.
    7. El-Bouri, Ahmed & Balakrishnan, Subramaniam & Popplewell, Neil, 2008. "Cooperative dispatching for minimizing mean flowtime in a dynamic flowshop," International Journal of Production Economics, Elsevier, vol. 113(2), pages 819-833, June.
    8. Tasgetiren, M. Fatih & Liang, Yun-Chia & Sevkli, Mehmet & Gencyilmaz, Gunes, 2007. "A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1930-1947, March.
    9. Mohamed Ali Rakrouki & Anis Kooli & Sabrine Chalghoumi & Talel Ladhari, 2020. "A branch-and-bound algorithm for the two-machine total completion time flowshop problem subject to release dates," Operational Research, Springer, vol. 20(1), pages 21-35, March.
    10. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    11. K Sheibani, 2010. "A fuzzy greedy heuristic for permutation flow-shop scheduling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(5), pages 813-818, May.
    12. Ali Gharaei & Fariborz Jolai, 2021. "A Pareto approach for the multi-factory supply chain scheduling and distribution problem," Operational Research, Springer, vol. 21(4), pages 2333-2364, December.
    13. Ruiz, Ruben & Maroto, Concepcion, 2006. "A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility," European Journal of Operational Research, Elsevier, vol. 169(3), pages 781-800, March.
    14. Ladhari, Talel & Rakrouki, Mohamed Ali, 2009. "Heuristics and lower bounds for minimizing the total completion time in a two-machine flowshop," International Journal of Production Economics, Elsevier, vol. 122(2), pages 678-691, December.
    15. Barry B. & Quim Castellà & Angel A. & Helena Ramalhinho Lourenco & Manuel Mateo, 2012. "ILS-ESP: An Efficient, Simple, and Parameter-Free Algorithm for Solving the Permutation Flow-Shop Problem," Working Papers 636, Barcelona School of Economics.
    16. Wang, Ling & Sun, Lin-Yan & Sun, Lin-Hui & Wang, Ji-Bo, 2010. "On three-machine flow shop scheduling with deteriorating jobs," International Journal of Production Economics, Elsevier, vol. 125(1), pages 185-189, May.
    17. Wen, Charlie & Eksioglu, Sandra Duni & Greenwood, Allen & Zhang, Shu, 2010. "Crane scheduling in a shipbuilding environment," International Journal of Production Economics, Elsevier, vol. 124(1), pages 40-50, March.
    18. Pan, Quan-Ke & Ruiz, Rubén, 2012. "Local search methods for the flowshop scheduling problem with flowtime minimization," European Journal of Operational Research, Elsevier, vol. 222(1), pages 31-43.
    19. Tseng, Lin-Yu & Lin, Ya-Tai, 2009. "A hybrid genetic local search algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 198(1), pages 84-92, October.
    20. Gerardo Minella & Rubén Ruiz & Michele Ciavotta, 2008. "A Review and Evaluation of Multiobjective Algorithms for the Flowshop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 451-471, August.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:proeco:v:112:y:2008:i:2:p:742-755. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/ijpe .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.