Lower bounds for single machine subproblems occurring in weighted tardiness oriented shifting bottleneck procedures

Roland Braune, Günther Zäpfel, Michael Affenzeller

Research output: Chapter in Book/Report/Conference proceedingsConference contribution

2 Citations (Scopus)

Abstract

In this paper, we propose lower bounds for single machine scheduling problems which occur during a run of a shifting bottleneck procedure for total weighted tardiness job shops. The specific structure of this kind of problem and its objective function in particular prevent an immediate transfer or an adaption of existing lower bounds from conventional single machine problems with tardiness related objectives. Hence it has been necessary to develop bounding approaches which are to some extent conceptually new. Potential application scenarios range from exact subproblem solution methods or machine prioritization criteria in a shifting bottleneck procedure to branch-and-bound algorithms for job shops with total weighted tardiness objective. In order to provide a significant evaluation of the proposed lower bounds regarding their effectiveness and efficiency, we tested them based on problem instances which actually have been generated in a shifting bottleneck procedure applied to benchmark job shop problems.

Original languageEnglish
Title of host publicationIEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011
Subtitle of host publication2011 IEEE Symposium on Computational Intelligence in Scheduling
PublisherIEEE Computational Intelligence Society
Pages25-32
Number of pages8
ISBN (Print)9781612841960
DOIs
Publication statusPublished - 2011
EventIEEE Symposium on Computational Intelligence in Scheduling - Paris, France
Duration: 11 Apr 201115 Apr 2011
http://www.ntu.edu.sg/home/epnsugan/index_files/SSCI2013/index.html

Publication series

NameIEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling

Conference

ConferenceIEEE Symposium on Computational Intelligence in Scheduling
CountryFrance
CityParis
Period11.04.201115.04.2011
Internet address

Fingerprint Dive into the research topics of 'Lower bounds for single machine subproblems occurring in weighted tardiness oriented shifting bottleneck procedures'. Together they form a unique fingerprint.

Cite this