IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v193y2009i1p73-85.html
   My bibliography  Save this article

A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times

Author

Listed:
  • Anghinolfi, Davide
  • Paolucci, Massimo

Abstract

In this paper we present a new Discrete Particle Swarm Optimization (DPSO) approach to face the NP-hard single machine total weighted tardiness scheduling problem in presence of sequence-dependent setup times. Differently from previous approaches the proposed DPSO uses a discrete model both for particle position and velocity and a coherent sequence metric. We tested the proposed DPSO mainly over a benchmark originally proposed by Cicirello in 2003 and available online. The results obtained show the competitiveness of our DPSO, which is able to outperform the best known results for the benchmark. In addition, we also tested the DPSO on a set of benchmark instances from ORLIB for the single machine total weighted tardiness problem, and we analysed the role of the DPSO swarm intelligence mechanisms as well as the local search intensification phase included in the algorithm.

Suggested Citation

  • Anghinolfi, Davide & Paolucci, Massimo, 2009. "A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 193(1), pages 73-85, February.
    • Handle: RePEc:eee:ejores:v:193:y:2009:i:1:p:73-85
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)01072-7
    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. Franca, Paulo M. & Mendes, Alexandre & Moscato, Pablo, 2001. "A memetic algorithm for the total tardiness single machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 132(1), pages 224-242, July.
    2. 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.
    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. Allahverdi, Ali, 2015. "The third comprehensive survey on scheduling problems with setup times/costs," European Journal of Operational Research, Elsevier, vol. 246(2), pages 345-378.
    2. Chen, Yin-Yann & Cheng, Chen-Yang & Wang, Li-Chih & Chen, Tzu-Li, 2013. "A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems—A case study for solar cell industry," International Journal of Production Economics, Elsevier, vol. 141(1), pages 66-78.
    3. Zeng, Ziqiang & Nasri, Ehsan & Chini, Abdol & Ries, Robert & Xu, Jiuping, 2015. "A multiple objective decision making model for energy generation portfolio under fuzzy uncertainty: Case study of large scale investor-owned utilities in Florida," Renewable Energy, Elsevier, vol. 75(C), pages 224-242.
    4. Mallor, Fermin & Guardiola, Ivan G., 2014. "The Weibull scheduling index for client driven manufacturing processes," International Journal of Production Economics, Elsevier, vol. 150(C), pages 225-238.
    5. Albert Corominas & Alberto García-Villoria & Rafael Pastor, 2013. "Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(2), pages 296-312, July.
    6. Zahra Beheshti & Siti Shamsuddin & Siti Yuhaniz, 2013. "Binary Accelerated Particle Swarm Algorithm (BAPSA) for discrete optimization problems," Journal of Global Optimization, Springer, vol. 57(2), pages 549-573, October.
    7. Jacomine Grobler & Andries Engelbrecht & Schalk Kok & Sarma Yadavalli, 2010. "Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times, auxiliary resources and machine down time," Annals of Operations Research, Springer, vol. 180(1), pages 165-196, November.
    8. Og[breve]uz, Ceyda & Sibel Salman, F. & Bilgintürk YalçIn, Zehra, 2010. "Order acceptance and scheduling decisions in make-to-order systems," International Journal of Production Economics, Elsevier, vol. 125(1), pages 200-211, May.
    9. Arthur Kramer & Anand Subramanian, 2019. "A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems," Journal of Scheduling, Springer, vol. 22(1), pages 21-57, February.
    10. Anzanello, Michel J. & Fogliatto, Flavio S. & Santos, Luana, 2014. "Learning dependent job scheduling in mass customized scenarios considering ergonomic factors," International Journal of Production Economics, Elsevier, vol. 154(C), pages 136-145.
    11. Miguel A. González & Juan José Palacios & Camino R. Vela & Alejandro Hernández-Arauzo, 2017. "Scatter search for minimizing weighted tardiness in a single machine scheduling with setups," Journal of Heuristics, Springer, vol. 23(2), pages 81-110, June.

    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. Jacomine Grobler & Andries Engelbrecht & Schalk Kok & Sarma Yadavalli, 2010. "Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times, auxiliary resources and machine down time," Annals of Operations Research, Springer, vol. 180(1), pages 165-196, November.
    3. Quang Chieu Ta & Jean-Charles Billaut & Jean-Louis Bouquard, 2018. "Matheuristic algorithms for minimizing total tardiness in the m-machine flow-shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 29(3), pages 617-628, March.
    4. S-W Lin & K-C Ying, 2008. "A hybrid approach for single-machine tardiness problems with sequence-dependent setup times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(8), pages 1109-1119, August.
    5. Pan, Quan-Ke & Gao, Liang & Li, Xin-Yu & Gao, Kai-Zhou, 2017. "Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times," Applied Mathematics and Computation, Elsevier, vol. 303(C), pages 89-112.
    6. Boonmee, Atiwat & Sethanan, Kanchana, 2016. "A GLNPSO for multi-level capacitated lot-sizing and scheduling problem in the poultry industry," European Journal of Operational Research, Elsevier, vol. 250(2), pages 652-665.
    7. Shesh Narayan Sahu & Yuvraj Gajpal & Swapan Debbarma, 2018. "Two-agent-based single-machine scheduling with switchover time to minimize total weighted completion time and makespan objectives," Annals of Operations Research, Springer, vol. 269(1), pages 623-640, October.
    8. Pagnozzi, Federico & Stützle, Thomas, 2019. "Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems," European Journal of Operational Research, Elsevier, vol. 276(2), pages 409-421.
    9. Raúl Mencía & Carlos Mencía, 2021. "One-Machine Scheduling with Time-Dependent Capacity via Efficient Memetic Algorithms," Mathematics, MDPI, vol. 9(23), pages 1-24, November.
    10. Tseng, Lin-Yu & Lin, Ya-Tai, 2010. "A genetic local search algorithm for minimizing total flowtime in the permutation flowshop scheduling problem," International Journal of Production Economics, Elsevier, vol. 127(1), pages 121-128, September.
    11. Tseng, Chao-Tang & Liao, Ching-Jong, 2008. "A discrete particle swarm optimization for lot-streaming flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 191(2), pages 360-373, December.
    12. Zhou, Hong & Cheung, Waiman & Leung, Lawrence C., 2009. "Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm," European Journal of Operational Research, Elsevier, vol. 194(3), pages 637-649, May.
    13. ElMekkawy, T.Y. & Liu, S., 2009. "A new memetic algorithm for optimizing the partitioning problem of tandem AGV systems," International Journal of Production Economics, Elsevier, vol. 118(2), pages 508-520, April.
    14. Fernandez-Viagas, Victor & Ruiz, Rubén & Framinan, Jose M., 2017. "A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation," European Journal of Operational Research, Elsevier, vol. 257(3), pages 707-721.
    15. Kalczynski, Pawel J. & Kamburowski, Jerzy, 2009. "An empirical analysis of the optimality rate of flow shop heuristics," European Journal of Operational Research, Elsevier, vol. 198(1), pages 93-101, October.
    16. 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.
    17. Chen, Yin-Yann & Cheng, Chen-Yang & Wang, Li-Chih & Chen, Tzu-Li, 2013. "A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems—A case study for solar cell industry," International Journal of Production Economics, Elsevier, vol. 141(1), pages 66-78.
    18. Öztürkoğlu, Ö. & Gue, K.R. & Meller, R.D., 2014. "A constructive aisle design model for unit-load warehouses with multiple pickup and deposit points," European Journal of Operational Research, Elsevier, vol. 236(1), pages 382-394.
    19. Benavides, Alexander J. & Ritt, Marcus & Miralles, Cristóbal, 2014. "Flow shop scheduling with heterogeneous workers," European Journal of Operational Research, Elsevier, vol. 237(2), pages 713-720.
    20. Berretta, Regina & Rodrigues, Luiz Fernando, 2004. "A memetic algorithm for a multistage capacitated lot-sizing problem," International Journal of Production Economics, Elsevier, vol. 87(1), pages 67-81, January.

    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:ejores:v:193:y:2009:i:1:p:73-85. 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/eor .

    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.