Combining sectional processing algorithm and compound incremental cost based list scheduling algorithm for long-horizon job-shop scheduling problems

Shin Yeu Lin, Jui Yen Cheng

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

Abstract

In this paper, we combine the sectional processing algorithm with the compound incremental cost based list scheduling algorithm to solve long-horizon job-shop scheduling problems. Our algorithm has achieved the reduction of both CPU times and objective values in comparing with the original method. In our simulation results, we observe that when the section length of our algorithm approximately equals the average system time, the reduction of both CPU times and objective values are approximately optimal. This observation leads us to proposing a receding horizon scheduling algorithm for infinite-horizon job-shop scheduling problems. This algorithm allows us to solve the scheduling problem one section at a time. Thus, it will not only save the computation time tremendously but also easily take care of the variation of the system configuration.

Original languageEnglish
Title of host publication2001 European Control Conference, ECC 2001
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1029-1033
Number of pages5
ISBN (Electronic)9783952417362
DOIs
StatePublished - 2001
Externally publishedYes
Event6th European Control Conference, ECC 2001 - Porto, Portugal
Duration: 04 09 200107 09 2001

Publication series

Name2001 European Control Conference, ECC 2001

Conference

Conference6th European Control Conference, ECC 2001
Country/TerritoryPortugal
CityPorto
Period04/09/0107/09/01

Bibliographical note

Publisher Copyright:
© 2001 EUCA.

Keywords

  • Job-shop scheduling
  • Lagrange relaxation method
  • heuristic algorithm
  • optimization
  • receding horizon

Fingerprint

Dive into the research topics of 'Combining sectional processing algorithm and compound incremental cost based list scheduling algorithm for long-horizon job-shop scheduling problems'. Together they form a unique fingerprint.

Cite this