| Title: |
A hybrid local search algorithm for the continuous energy-constrained scheduling problem |
| Authors: |
Brouwer, Roel; van den Akker, Marjan; Hoogeveen, Han; Sub Algorithms and Complexity; Sub Simulation of Complex Systems; Sub Algorithmic Data Analysis; Algorithms and Complexity |
| Publication Year: |
2025 |
| Subject Terms: |
Continuous scheduling; Mixed-integer linear programming; Resource-constrained scheduling; Simulated annealing; Software; General Engineering; Management Science and Operations Research; Artificial Intelligence |
| Description: |
We consider the continuous energy-constrained scheduling problem (CECSP). A set of jobs has to be processed on a continuous, shared resource. A schedule for a job consists of a start time, completion time, and a resource consumption profile. The goal is to find a schedule such that each job does not start before its release time, is completed before its deadline, satisfies its full resource requirement, and respects its lower and upper bounds on resource consumption during processing. The objective is to minimize the total weighted completion time. We present a hybrid local search approach, using simulated annealing and linear programming, and compare it to a mixed-integer linear programming (MILP) formulation. We show that the hybrid local search approach matches the MILP formulation in solution quality for small instances and is able to find a feasible solution for larger instances in reasonable time. |
| Document Type: |
article in journal/newspaper |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
1094-6136 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/473720 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/473720 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.AEA56B9B |
| Database: |
BASE |