📆 Embargo bis 2024-08-31
Konferenzveröffentlichung
Propagation and branching strategies for job shop scheduling minimizing the weighted energy consumption
Zusammenfassung
We consider a job shop scheduling problem with time windows, flexible energy prices, and machines whose energy consumption depends on their operational state (offline, ramp-up, setup, processing, standby or ramp-down). The goal is to find a valid schedule that minimizes the overall energy cost. To solve this problem to optimality, we developed a branch-and-bound algorithm based on a time-indexed integer linear programming (ILP) formulation, which uses binary variables that describe blocks spanning multiple inactive periods on the machines. In this paper, we discuss the propagation and branching schemes used in that algorithm. The strategies, which are specifically tailored for energy related machine scheduling problems, primarily aim to determine and sharpen the activity profiles of the machines (and thus reduce the number of the inactive block variables) and address the workload profile of the tasks with lower priority.
Zusätzliche Informationen
Erschienen in: Grothe, O., Nickel, S., Rebennack, S., Stein, O. (eds) Operations Research Proceedings 2022. OR 2022. Lecture Notes in Operations Research. Springer, Cham. https://doi.org/10.1007/978-3-031-24907-5_68Zitieren
@inproceedings{doi:10.17170/kobra-202311108997,
author={Bley, Andreas and Linß, Andreas},
title={Propagation and branching strategies for job shop scheduling minimizing the weighted energy consumption},
year={2023}
}
0500 Oax
0501 Text $btxt$2rdacontent
0502 Computermedien $bc$2rdacarrier
1100 2023$n2023
1500 1/eng
2050 ##0##http://hdl.handle.net/123456789/15180
3000 Bley, Andreas
3010 Linß, Andreas
4000 Propagation and branching strategies for job shop scheduling minimizing the weighted energy consumption / Bley, Andreas
4030
4060 Online-Ressource
4085 ##0##=u http://nbn-resolving.de/http://hdl.handle.net/123456789/15180=x R
4204 \$dKonferenzveröffentlichung
4170
5550 {{Ganzzahlige Optimierung}}
5550 {{Branch-and-Bound-Methode}}
5550 {{Reihenfolgeproblem}}
5550 {{Energieverbrauch}}
7136 ##0##http://hdl.handle.net/123456789/15180
<resource xsi:schemaLocation="http://datacite.org/schema/kernel-2.2 http://schema.datacite.org/meta/kernel-2.2/metadata.xsd"> 2023-11-15T08:50:45Z 2023 doi:10.17170/kobra-202311108997 http://hdl.handle.net/123456789/15180 Erschienen in: Grothe, O., Nickel, S., Rebennack, S., Stein, O. (eds) Operations Research Proceedings 2022. OR 2022. Lecture Notes in Operations Research. Springer, Cham. https://doi.org/10.1007/978-3-031-24907-5_68 eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ integer programming machine scheduling presolving branch and bound 510 Propagation and branching strategies for job shop scheduling minimizing the weighted energy consumption Konferenzveröffentlichung We consider a job shop scheduling problem with time windows, flexible energy prices, and machines whose energy consumption depends on their operational state (offline, ramp-up, setup, processing, standby or ramp-down). The goal is to find a valid schedule that minimizes the overall energy cost. To solve this problem to optimality, we developed a branch-and-bound algorithm based on a time-indexed integer linear programming (ILP) formulation, which uses binary variables that describe blocks spanning multiple inactive periods on the machines. In this paper, we discuss the propagation and branching schemes used in that algorithm. The strategies, which are specifically tailored for energy related machine scheduling problems, primarily aim to determine and sharpen the activity profiles of the machines (and thus reduce the number of the inactive block variables) and address the workload profile of the tasks with lower priority. restricted access Bley, Andreas Linß, Andreas 7 Seiten Ganzzahlige Optimierung Branch-and-Bound-Methode Reihenfolgeproblem Energieverbrauch submittedVersion 2022-09-06 - 2022-09-09 Karlsruhe 2024-08-31 2024-08-31 false Operations Research Society of Germany </resource>
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden:
:Urheberrechtlich geschützt