View/ Open
Date
2023Subject
510 Mathematics Ganzzahlige OptimierungBranch-and-Bound-MethodeReihenfolgeproblemEnergieverbrauchMetadata
Show full item record
Konferenzveröffentlichung![](/themes/Mirage2/images/Open_Access_logo_PLoS_transparent.svg)
Propagation and branching strategies for job shop scheduling minimizing the weighted energy consumption
Abstract
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.
Additional Information
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_68Citation
@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
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. open access Bley, Andreas Linß, Andreas 7 Seiten Ganzzahlige Optimierung Branch-and-Bound-Methode Reihenfolgeproblem Energieverbrauch submittedVersion 2022-09-06 - 2022-09-09 Karlsruhe false Operations Research Society of Germany
The following license files are associated with this item:
Urheberrechtlich geschützt