A heuristic algorithm for the just-in-time single machine scheduling problem with setups: a comparison with simulated annealing

    Authors

    G. Rabadi; G. C. Anagnostopoulos;M. Mollaghasemi

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Int. J. Adv. Manuf. Technol.

    Keywords

    simulated annealing; scheduling; single machine; setup time; early-tardy; problem; common due date; COMMON DUE-DATE; SEQUENCE-DEPENDENT SETUP; COMPLETION TIMES; ABSOLUTE; DEVIATION; GENETIC ALGORITHM; JOB FAMILIES; TARDINESS; PENALTIES; PROCESSOR; EARLINESS; Automation & Control Systems; Engineering, Manufacturing

    Abstract

    This paper addresses the single machine early/tardy problem with unrestricted common due date and sequence-dependent setup times. Two algorithms are introduced to reach near-optimum solutions: the SAPT, a heuristic tailored for the problem, and a simulated annealing (SA) algorithm. It will be shown that SA provides solutions with slightly better quality; however, SAPT requires much less computational time. SAPT-SA is a hybrid heuristic that combines both approaches to obtain high quality solutions with low computational cost. Solutions provided by the three algorithms were compared to optimal solutions for problems with up to 25 jobs and to each other for larger problems.

    Journal Title

    International Journal of Advanced Manufacturing Technology

    Volume

    32

    Issue/Number

    3-4

    Publication Date

    1-1-2007

    Document Type

    Article

    Language

    English

    First Page

    326

    Last Page

    335

    WOS Identifier

    WOS:000244487300011

    ISSN

    0268-3768

    Share

    COinS