Author name cluster

Dimitrios Letsios

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

ECAI Conference 2025 Conference Paper

Argumentation for Explainable Workforce Optimisation

Jennifer Leigh
Dimitrios Letsios
Alessandro Mella
Lucio Machetti
Francesca Toni

Workforce management is a complex problem involving the optimisation of the makespan and travel distance required for a team of operators to complete a set of jobs, using a set of instruments. A crucial challenge in workforce management is accommodating changes at execution time so that explanations are provided to all stakeholders involved. Here, we show that, by understanding workforce management as abstract argumentation in an industrial application, we can accommodate change and obtain faithful explanations. We show, with a user study, that our tool and explanations lead to faster and more accurate problem solving than conventional manual approaches.

Details

TCS Journal 2024 Journal Article

New bounds for single-machine time-dependent scheduling with uniform deterioration

Angelos Gkikas
Dimitrios Letsios
Tomasz Radzik
Kathleen Steinhöfel

We consider the single-machine time-dependent scheduling problem with linearly deteriorating jobs arriving over time. Each job i is associated with a release time r i and a processing time p i ( s i ) = α i + β i s i, where α i, β i > 0 are parameters and s i is the job's start time. In this setting, the approximability of both single-machine minimum makespan and total completion time problems remains open. We develop new bounds and approximation results for the special case of the problems with uniform deterioration, i. e. β i = β, for each i. The main contribution is a O ( 1 + 1 / β ) -approximation algorithm for the makespan problem and a O ( 1 + 1 / β 2 ) approximation algorithm for the total completion time problem. Further, we propose greedy constant-factor approximation algorithms for instances with β = O ( 1 / n ) and β = Ω ( n ), where n is the number of jobs. Our analysis is based on an approach for comparing computed and optimal schedules via bounding pseudomatchings.

Details DOI

AAAI Conference 2019 Conference Paper

Argumentation for Explainable Scheduling

Kristijonas Čyras
Dimitrios Letsios
Ruth Misener
Francesca Toni

Mathematical optimization offers highly-effective tools for finding solutions for problems with well-defined goals, notably scheduling. However, optimization solvers are often unexplainable black boxes whose solutions are inaccessible to users and which users cannot interact with. We define a novel paradigm using argumentation to empower the interaction between optimization solvers and users, supported by tractable explanations which certify or refute solutions. A solution can be from a solver or of interest to a user (in the context of ’what-if’ scenarios). Specifically, we define argumentative and natural language explanations for why a schedule is (not) feasible, (not) efficient or (not) satisfying fixed user decisions, based on models of the fundamental makespan scheduling problem in terms of abstract argumentation frameworks (AFs). We define three types of AFs, whose stable extensions are in one-to-one correspondence with schedules that are feasible, efficient and satisfying fixed decisions, respectively. We extract the argumentative explanations from these AFs and the natural language explanations from the argumentative ones.

PDF Details

I&C Journal 2017 Journal Article

Scheduling on power-heterogeneous processors

Susanne Albers
Evripidis Bampis
Dimitrios Letsios
Giorgio Lucarelli
Richard Stotz

We consider the problem of scheduling a set of jobs, each one specified by its release date, its deadline and its processing volume, on a set of heterogeneous speed-scalable processors, where the energy-consumption rate is processor-dependent. Our objective is to minimize the total energy consumption when both the preemption and the migration of jobs are allowed. We propose a new algorithm based on a compact linear programming formulation. Our method approaches the value of the optimal solution within any desired accuracy for a large set of continuous power functions. Furthermore, we develop a faster combinatorial algorithm based on flows for standard power functions and jobs whose density is lower bounded by a small constant. Finally, we extend and analyze the AVerage Rate (AVR) online algorithm in the heterogeneous setting.

Details DOI

TCS Journal 2015 Journal Article

Green scheduling, flows and matchings

Evripidis Bampis
Dimitrios Letsios
Giorgio Lucarelli

Recently, optimal combinatorial algorithms have been presented for the energy minimization multiprocessor speed-scaling problem with migrations [5, 7]. These algorithms use repeated maximum-flow computations that allow the partition of the set of jobs into subsets in which all the jobs are executed at the same speed. The optimality of these algorithms is based on a series of technical lemmas showing that this partition and the corresponding speeds lead to the minimization of the energy consumption. In this paper, we show that both the algorithms and their analysis can be greatly simplified. In order to do this, we formulate the problem as a convex cost flow problem in an appropriate flow network. Furthermore, we show that our approach is useful to solve other problems in the dynamic speed-scaling setting. As an example, we consider the preemptive open-shop speed-scaling problem and we propose a polynomial-time algorithm for finding an optimal solution based on the computation of convex cost flows. We also propose a polynomial-time algorithm for minimizing a linear combination of the sum of the completion times of the jobs and the total energy consumption, for the non-preemptive multiprocessor speed-scaling problem. Instead of using convex cost flows, our algorithm is based on the computation of a minimum weighted maximum matching in an appropriate bipartite graph.

Details DOI