A hybrid local search algorithm for the Continuous Energy-Constrained Scheduling Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910649921044480 |
|---|---|
| author | Brouwer, Roel Akker, Marjan van den Hoogeveen, Han |
| author_facet | Brouwer, Roel Akker, Marjan van den Hoogeveen, Han |
| contents | 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. We want 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. Our 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_16177 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A hybrid local search algorithm for the Continuous Energy-Constrained Scheduling Problem Brouwer, Roel Akker, Marjan van den Hoogeveen, Han Optimization and Control 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. We want 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. Our 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. |
| title | A hybrid local search algorithm for the Continuous Energy-Constrained Scheduling Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2311.16177 |