VNS-Based Heuristic for Identical Parallel Machine Scheduling Problem

S Bathrinath, S Saravana Sankar, Sivalinga Govinda Ponnambalam, I Jerin Leno

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    3 Citations (Scopus)

    Abstract

    Minimization of make span and minimization of number of tardy jobs in identical parallel machine scheduling problems are proved to be NP-hard problems. Many researchers have attempted to solve these combinatorial optimization problems by employing different heuristic algorithms. While providing a satisfactory solution to the production environment for each of the above-said objectives, still remains as a challenge, most of the time, the need has been to have satisfactory solutions optimizing simultaneously the above-said two objectives. In this research work, an attempt is made to address this issue and heuristic algorithms using simulated annealing algorithm (SA) and variable neighborhood search algorithm (VNS) have been developed to provide near-optimal solutions. The developed heuristics are tested for their efficiency on a very large data sets generated as per the prescribed procedure found in the literature. Based on the results of experiments, it is inferred that the VNS-based heuristics outperforms the SA-based heuristics consistently both in terms of solution quality and consistency.
    Original languageEnglish
    Title of host publicationProceedings of the International Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES)
    EditorsL Padma Suresh, Subhransu Sekhar Dash, Bijaya Ketan Panigrahi
    Place of PublicationBerlin Germany
    PublisherSpringer-Verlag London Ltd.
    Pages693 - 699
    Number of pages7
    Volume324
    ISBN (Print)9788132221258
    DOIs
    Publication statusPublished - 2015
    EventInternational Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES) - Kumaracoil India, Berlin Germany
    Duration: 1 Jan 2015 → …

    Conference

    ConferenceInternational Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES)
    CityBerlin Germany
    Period1/01/15 → …

    Cite this

    Bathrinath, S., Sankar, S. S., Ponnambalam, S. G., & Leno, I. J. (2015). VNS-Based Heuristic for Identical Parallel Machine Scheduling Problem. In L. P. Suresh, S. S. Dash, & B. K. Panigrahi (Eds.), Proceedings of the International Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES) (Vol. 324, pp. 693 - 699). Berlin Germany: Springer-Verlag London Ltd.. https://doi.org/10.1007/978-81-322-2126-5_74
    Bathrinath, S ; Sankar, S Saravana ; Ponnambalam, Sivalinga Govinda ; Leno, I Jerin. / VNS-Based Heuristic for Identical Parallel Machine Scheduling Problem. Proceedings of the International Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES). editor / L Padma Suresh ; Subhransu Sekhar Dash ; Bijaya Ketan Panigrahi. Vol. 324 Berlin Germany : Springer-Verlag London Ltd., 2015. pp. 693 - 699
    @inproceedings{27437ddb8b42432686bb413193de137d,
    title = "VNS-Based Heuristic for Identical Parallel Machine Scheduling Problem",
    abstract = "Minimization of make span and minimization of number of tardy jobs in identical parallel machine scheduling problems are proved to be NP-hard problems. Many researchers have attempted to solve these combinatorial optimization problems by employing different heuristic algorithms. While providing a satisfactory solution to the production environment for each of the above-said objectives, still remains as a challenge, most of the time, the need has been to have satisfactory solutions optimizing simultaneously the above-said two objectives. In this research work, an attempt is made to address this issue and heuristic algorithms using simulated annealing algorithm (SA) and variable neighborhood search algorithm (VNS) have been developed to provide near-optimal solutions. The developed heuristics are tested for their efficiency on a very large data sets generated as per the prescribed procedure found in the literature. Based on the results of experiments, it is inferred that the VNS-based heuristics outperforms the SA-based heuristics consistently both in terms of solution quality and consistency.",
    author = "S Bathrinath and Sankar, {S Saravana} and Ponnambalam, {Sivalinga Govinda} and Leno, {I Jerin}",
    year = "2015",
    doi = "10.1007/978-81-322-2126-5_74",
    language = "English",
    isbn = "9788132221258",
    volume = "324",
    pages = "693 -- 699",
    editor = "Suresh, {L Padma} and Dash, {Subhransu Sekhar} and Panigrahi, {Bijaya Ketan}",
    booktitle = "Proceedings of the International Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES)",
    publisher = "Springer-Verlag London Ltd.",
    address = "Germany",

    }

    Bathrinath, S, Sankar, SS, Ponnambalam, SG & Leno, IJ 2015, VNS-Based Heuristic for Identical Parallel Machine Scheduling Problem. in LP Suresh, SS Dash & BK Panigrahi (eds), Proceedings of the International Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES). vol. 324, Springer-Verlag London Ltd., Berlin Germany, pp. 693 - 699, International Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES), Berlin Germany, 1/01/15. https://doi.org/10.1007/978-81-322-2126-5_74

    VNS-Based Heuristic for Identical Parallel Machine Scheduling Problem. / Bathrinath, S; Sankar, S Saravana; Ponnambalam, Sivalinga Govinda; Leno, I Jerin.

    Proceedings of the International Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES). ed. / L Padma Suresh; Subhransu Sekhar Dash; Bijaya Ketan Panigrahi. Vol. 324 Berlin Germany : Springer-Verlag London Ltd., 2015. p. 693 - 699.

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    TY - GEN

    T1 - VNS-Based Heuristic for Identical Parallel Machine Scheduling Problem

    AU - Bathrinath, S

    AU - Sankar, S Saravana

    AU - Ponnambalam, Sivalinga Govinda

    AU - Leno, I Jerin

    PY - 2015

    Y1 - 2015

    N2 - Minimization of make span and minimization of number of tardy jobs in identical parallel machine scheduling problems are proved to be NP-hard problems. Many researchers have attempted to solve these combinatorial optimization problems by employing different heuristic algorithms. While providing a satisfactory solution to the production environment for each of the above-said objectives, still remains as a challenge, most of the time, the need has been to have satisfactory solutions optimizing simultaneously the above-said two objectives. In this research work, an attempt is made to address this issue and heuristic algorithms using simulated annealing algorithm (SA) and variable neighborhood search algorithm (VNS) have been developed to provide near-optimal solutions. The developed heuristics are tested for their efficiency on a very large data sets generated as per the prescribed procedure found in the literature. Based on the results of experiments, it is inferred that the VNS-based heuristics outperforms the SA-based heuristics consistently both in terms of solution quality and consistency.

    AB - Minimization of make span and minimization of number of tardy jobs in identical parallel machine scheduling problems are proved to be NP-hard problems. Many researchers have attempted to solve these combinatorial optimization problems by employing different heuristic algorithms. While providing a satisfactory solution to the production environment for each of the above-said objectives, still remains as a challenge, most of the time, the need has been to have satisfactory solutions optimizing simultaneously the above-said two objectives. In this research work, an attempt is made to address this issue and heuristic algorithms using simulated annealing algorithm (SA) and variable neighborhood search algorithm (VNS) have been developed to provide near-optimal solutions. The developed heuristics are tested for their efficiency on a very large data sets generated as per the prescribed procedure found in the literature. Based on the results of experiments, it is inferred that the VNS-based heuristics outperforms the SA-based heuristics consistently both in terms of solution quality and consistency.

    UR - http://www.springer.com/us/book/9788132221258#aboutAuthors

    U2 - 10.1007/978-81-322-2126-5_74

    DO - 10.1007/978-81-322-2126-5_74

    M3 - Conference Paper

    SN - 9788132221258

    VL - 324

    SP - 693

    EP - 699

    BT - Proceedings of the International Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES)

    A2 - Suresh, L Padma

    A2 - Dash, Subhransu Sekhar

    A2 - Panigrahi, Bijaya Ketan

    PB - Springer-Verlag London Ltd.

    CY - Berlin Germany

    ER -

    Bathrinath S, Sankar SS, Ponnambalam SG, Leno IJ. VNS-Based Heuristic for Identical Parallel Machine Scheduling Problem. In Suresh LP, Dash SS, Panigrahi BK, editors, Proceedings of the International Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES). Vol. 324. Berlin Germany: Springer-Verlag London Ltd. 2015. p. 693 - 699 https://doi.org/10.1007/978-81-322-2126-5_74