1610. Single-machine scheduling with fixed energy recharging times to minimize the number of late jobs and the number of just-in-time jobs: a parameterized complexity analysis
Invited abstract in session WA-21: Metaheuristics for Scheduling and Production, stream Metaheuristics .
Wednesday, 8:30-10:00Room: Esther Simpson 2.12
Authors (first author is the speaker)
| 1. | Renjie Yu
|
| Business School, The University of Sydney | |
| 2. | Daniel Oron
|
| Business Analytics, The University of Sydney |
Abstract
We study single-machine scheduling problems where processing each job requires both processing time and rechargeable energy. Subject to a predefined energy capacity, energy can be recharged after each job during a fixed recharging period. Our focus is on two due date-related scheduling criteria: minimizing the number of late jobs and maximizing the weighted number of jobs completed exactly at their due dates. We analyze the parameterized tractability of the two problems and develop fixed-parameter algorithms with respect to three natural parameters: the number of different due dates, the number of different processing times, and the number of different energy consumptions.
Keywords
- Scheduling
- Combinatorial Optimization
- Algorithms
Status: accepted
Back to the list of papers