GA-based discrete dynamic programming approach for scheduling in FMS environments

    Research output: Contribution to journalArticlepeer-review


    This paper presents a new genetic algorithm (GA)-based discrete dynamic programming (DDP) approach for generating static schedules in a flexible manufacturing system (FMS) environment. This GA-DDP approach adopts a sequence-dependent schedule generation strategy, where a GA is employed to generate feasible job sequences and a series of discrete dynamic programs are constructed to generate legal schedules for a given sequence of jobs. In formulating the GA, different performance criteria could be easily included. The developed DDP algorithm is capable of identifying locally optimized partial schedules and shares the computation efficiency of dynamic programming. The algorithm is designed in such a way that it does not suffer from the state explosion problem inherent in pure dynamic programming approaches in FMS scheduling. Numerical examples are reported to illustrate the approach.
    Original languageEnglish
    Pages (from-to)824-835
    Number of pages11
    JournalIEEE Transactions on Systems, Man, and Cybernetics. Part B: Cybernetics
    Issue number5
    Publication statusPublished - Oct 2001


    • Dynamic programming
    • Flexible manufacturing system (FMS)
    • Genetic algorithms (GAs)
    • Heuristics
    • Scheduling


    Dive into the research topics of 'GA-based discrete dynamic programming approach for scheduling in FMS environments'. Together they form a unique fingerprint.

    Cite this