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

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

doi:10.1109/SCIS.2011.5976548

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 proceedings › Conference 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 language	English
Title of host publication	IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011
Subtitle of host publication	2011 IEEE Symposium on Computational Intelligence in Scheduling
Publisher	IEEE Computational Intelligence Society
Pages	25-32
Number of pages	8
ISBN (Print)	9781612841960
DOIs	https://doi.org/10.1109/SCIS.2011.5976548
Publication status	Published - 2011
Event	IEEE Symposium on Computational Intelligence in Scheduling - Paris, France Duration: 11 Apr 2011 → 15 Apr 2011 http://www.ntu.edu.sg/home/epnsugan/index_files/SSCI2013/index.html

Publication series

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

Conference

Conference	IEEE Symposium on Computational Intelligence in Scheduling
Country/Territory	France
City	Paris
Period	11.04.2011 → 15.04.2011
Internet address	http://www.ntu.edu.sg/home/epnsugan/index_files/SSCI2013/index.html

Access to Document

10.1109/SCIS.2011.5976548

Cite this

Braune, R., Zäpfel, G., & Affenzeller, M. (2011). Lower bounds for single machine subproblems occurring in weighted tardiness oriented shifting bottleneck procedures. In IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling (pp. 25-32). Article 5976548 (IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling). IEEE Computational Intelligence Society. https://doi.org/10.1109/SCIS.2011.5976548

Braune, Roland ; Zäpfel, Günther ; Affenzeller, Michael. / Lower bounds for single machine subproblems occurring in weighted tardiness oriented shifting bottleneck procedures. IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling. IEEE Computational Intelligence Society, 2011. pp. 25-32 (IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling).

@inproceedings{4f05228f7d694f978ad42d0793112f4b,

title = "Lower bounds for single machine subproblems occurring in weighted tardiness oriented shifting bottleneck procedures",

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.",

author = "Roland Braune and G{\"u}nther Z{\"a}pfel and Michael Affenzeller",

year = "2011",

doi = "10.1109/SCIS.2011.5976548",

language = "English",

isbn = "9781612841960",

series = "IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling",

publisher = "IEEE Computational Intelligence Society",

pages = "25--32",

booktitle = "IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011",

address = "United States",

note = "IEEE Symposium on Computational Intelligence in Scheduling ; Conference date: 11-04-2011 Through 15-04-2011",

url = "http://www.ntu.edu.sg/home/epnsugan/index_files/SSCI2013/index.html",

}

Braune, R, Zäpfel, G & Affenzeller, M 2011, Lower bounds for single machine subproblems occurring in weighted tardiness oriented shifting bottleneck procedures. in IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling., 5976548, IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling, IEEE Computational Intelligence Society, pp. 25-32, IEEE Symposium on Computational Intelligence in Scheduling, Paris, France, 11.04.2011. https://doi.org/10.1109/SCIS.2011.5976548

Lower bounds for single machine subproblems occurring in weighted tardiness oriented shifting bottleneck procedures. / Braune, Roland; Zäpfel, Günther; Affenzeller, Michael.
IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling. IEEE Computational Intelligence Society, 2011. p. 25-32 5976548 (IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling).

Research output: Chapter in Book/Report/Conference proceedings › Conference contribution

TY - GEN

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

AU - Braune, Roland

AU - Zäpfel, Günther

AU - Affenzeller, Michael

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=80052086308&partnerID=8YFLogxK

U2 - 10.1109/SCIS.2011.5976548

DO - 10.1109/SCIS.2011.5976548

M3 - Conference contribution

SN - 9781612841960

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

SP - 25

EP - 32

BT - IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011

PB - IEEE Computational Intelligence Society

T2 - IEEE Symposium on Computational Intelligence in Scheduling

Y2 - 11 April 2011 through 15 April 2011

ER -

Braune R, Zäpfel G, Affenzeller M. Lower bounds for single machine subproblems occurring in weighted tardiness oriented shifting bottleneck procedures. In IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling. IEEE Computational Intelligence Society. 2011. p. 25-32. 5976548. (IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011: 2011 IEEE Symposium on Computational Intelligence in Scheduling). doi: 10.1109/SCIS.2011.5976548

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this