Highlight your achievements on People@HES-SO More info
PEOPLE@HES-SO – Directory and Skills inventory
PEOPLE@HES-SO – Directory and Skills inventory

PEOPLE@HES-SO
Directory and Skills inventory

Help
language
  • fr
  • en
  • de
  • fr
  • en
  • de
  • SWITCH edu-ID
  • Administration
ID
« Back
Schindl David

Schindl David

Maître d'enseignement HES

Main skills

Timetabling

Production planning

Combinatorial Optimization

Graph Theory

  • Contact

  • Teaching

  • Publications

  • Conferences

Main contract

Maître d'enseignement HES

Desktop: B 1.06

Haute école de gestion de Genève
Campus Battelle, Rue de la Tambourine 17, 1227 Carouge, CH
HEG-GE
Faculty
Economie et services
Main Degree Programme
Economie d'entreprise
BSc HES-SO en Economie d'entreprise - Haute école de gestion de Genève
  • Mathématiques et Statistiques
BSc HES-SO en Informatique de gestion - Haute école de gestion de Genève
  • Recherche Opérationnelle
Swiss Joint Master of Science in Computer Science - Université de Fribourg
  • Graph Theory and Applications

2024

Finding k-community structures in special graph classes
Scientific paper ArODES

Narmina Baghirova, Clément Dallard, Bernard Ries, David Schindl

Discrete applied mathematics,  2024, 359, 159-175

Link to the publication

Summary:

For an integer k ≥ 2, a k-community structure in an undirected graph is a partition of its vertex set into k sets called communities, each of size at least two, such that every vertex of the graph has proportionally at least as many neighbours in its own community as in any other community. In this paper, we give a necessary and sufficient condition for a forest on n vertices to admit a k-community structure. Furthermore, we provide an O(k2 ・ n2)-time algorithm that computes such a k-community structure in a forest, if it exists. These results extend a result of Bazgan et al., 2018. We also show that if communities are allowed to have size one, then every forest with n ≥ k ≥ 2 vertices admits a k-community structure that can be found in time O(k2 ・ n2). We then consider threshold graphs and show that every connected threshold graph admits a 2-community structure if and only if it is not isomorphic to a star; also if such a 2-community structure exists, we explain how to obtain it in linear time. We further describe an infinite family of disconnected threshold graphs, containing exactly one isolated vertex, that do not admit any 2-community structure. Finally, we present a new infinite family of connected graphs that may contain an even or an odd number of vertices without 2-community structures, even if communities are allowed to have size one.

2019

Optimal student sectioning on mandatory courses with various sections numbers
Scientific paper ArODES

David Schindl

Annals of operations research,  2019, vol. 275, Issue 1, pp 209–221

Link to the publication

Summary:

In sufficiently large schools, courses are given to classes in sections of various sizes. Consequently, classes have to be split into various given numbers of sections. We focus on how to dispatch the students into sections of equal size, so as to minimize the number of edges in the resulting conflict graph. As a main result, we show that subdividing the students set in a regular way is optimal. We then discuss our solution uniqueness and feasibility, as well as practical issues concerning teacher assignments to sections and the case of an additional course with unequal section sizes requirements.

2015

A learning tabu search for a truck allocation problem with linear and nonlinear cost components
Scientific paper ArODES

David Schindl, Nicolas Zufferey

Naval research logistics,  2015, vol. 62, no. 1, pp. 32-45

Link to the publication

Summary:

The two-level problem studied in this paper consists of optimizing the refueling costs of a fleet of locomotives over a railway network. The goal consists of determining: (1) the number of refueling trucks contracted for each yard (truck assignment problem denoted TAP), and (2) the refueling plan of each locomotive (fuel distribution problem denoted FDP). As the FDP can be solved efficiently with existing methods, the focus is put on the TAP only. In a first version of the problem (denoted (P1)), various linear costs (e.g., fuel, fixed cost associated with each refueling, weekly operating costs of trucks) have to be minimized while satisfying a set of constraints (e.g., limited capacities of the locomotives and the trucks). In contrast with the existing literature on this problem, two types of nonlinear cost components will also be considered, based on the following ideas: (1) if several trucks from the same fuel supplier are contracted for the same yard, the supplier is likely to propose discounted prices for that yard (problem (P2)); (2) if a train stops too often on its route, a penalty is incurred, which represents the dissatisfaction of the clients (problem (P3)). Even if exact methods based on a MILP formulation are available for (P1), they are not appropriate anymore to tackle (P2) and (P3). Various methods are proposed for the TAP: a descent local search, a tabu search, and al earning tabu search (LTS). The latter is a new type of local search algorithm. It involves a learning process relying on a trail system, and it can be applied to any combinatorial optimization problem. Results are reported and discussed for a large set of instances (for (P1), (P2) and (P3)), and show the good performance of LTS.

2009

Staff assignment using network flow techniques
Report ArODES

Sacha Varone, David Schindl

Genève : Haute école de gestion de Genève, 2009. 10 p. Cahier de recherche no HES-SO/HEG-GE/C--09/7/1--CH

Link to the publication

2024

A benders decomposition approach for a capacitated multivehicle covering tour problem with intermediate facilities
Conference ArODES

Vera Fischer, Antoine Legrain, David Schindl

Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Link to the conference

Summary:

We consider a waste collection problem with intermediate disposal facilities to accommodate the usage of smaller, but more sustainable vehicles, with less capacity than the traditional waste collecting trucks. The optimization problem consists in determining the locations to place the collection points and the routes of a capacitated collection vehicle that visits these locations. We first present a mixed-integer linear programming formulation that exploits the sparsity of the road network. To efficiently solve practical instances, we propose a Benders decomposition approach in which a set covering problem to select the collection points is solved in the master problem and a capacitated vehicle routing problem with intermediate facilities to determine the routes and price the set covering solution is solved in the subproblem. We show a way to derive valid Benders cuts when solving the Benders subproblem with column generation and propose a heuristic Benders approach that provides better solutions for larger instances and approximated lower bounds to assess the quality of the obtained solutions.

2021

Flexible job shop scheduling problem with sequence-dependent transportation constraints and setup times
Conference ArODES

Sacha Varone, David Schindl, Corentin Beffa

Position and Communication Papers of the 16th Conference on Computer Science and Intelligence Systems - Annals of Computer Science and Information Systems

Link to the conference

Summary:

We study a production scheduling problem, which adresses on the one hand the usual operational constraints such as the precedence of operations, time windows, delays, uniqueness of treatment, availability of resources, and waiting times. On the other hand, the problem takes into account possible restricted movements according to production orders. This problem is a variant of a flexible job shop scheduling problem with several types of sequence-dependent constraints. We consider additional sequence-dependent setup times, as well as sequence-dependent transportation and assignment restrictions. We propose a mixed integer programming model (MIP). It is based on the MIP model of a flexible job shop scheduling problem, in which we add those sequence-dependent constraints. We solve it with a general purpose MIP solver.

2016

Student sectioning for minimizing potential conflicts on multi-section courses
Conference ArODES

David Schindl

Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling (PATAT 2016)

Link to the conference

Summary:

In sufficiently large schools, lessons are given to classes in sections of various sizes, depending on the subject taught. Consequently, classes have to be split into various given numbers of sections. We focus on how to subdivide a class in subgroups, so as to be able to reproduce all required sections by merging subgroups together, while minimizing the number of edges in the resulting course conflict graph. As a main result, we show that subdividing the students set in a regular way is optimal. We then discuss our solution uniqueness and feasibility, as well as practical issues concerning teacher assignments to sections.

2013

Course opening, assignment and timetabling with student preferences
Conference ArODES

Sacha Varone, David Schindl

In : proceedings of International Conference on Operations Research and Enterprise Systems (ICORES)2013, 2013, Barcelona, Spain, 16-18 february

Link to the conference

Achievements

Media and communication
Contact us
Follow the HES-SO
linkedin instagram facebook twitter youtube rss
univ-unita.eu www.eua.be swissuniversities.ch
Legal Notice
© 2021 - HES-SO.

HES-SO Rectorat