Towards a tropical automaton product minimizing global completion times
- PDF / 2,273,058 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 193 Views
Towards a tropical automaton product minimizing global completion times Karla Quintero1 · Jose Aguilar2,3 · Eric Niel1 · Laurent Pietrac1 Received: 27 July 2019 / Revised: 20 May 2020 / Accepted: 26 May 2020 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2020
Abstract The main contribution of this paper is oriented towards system modeling with resource conflicts, in which a set of tasks must be completed at the earliest. Mutual exclusion between tasks with underlying resource conflicts is modeled as subsystems through local tropical automata. Parallel task execution is explored through a new framework for a synchronous product of tropical automata directly minimizing the global completion time of a set of tasks. A dater-based analysis is proposed to determine an optimal qualitative schedule and relies on proposed definitions of global, private, and synchronizing daters. This approach drastically narrows the solution spectrum, and allows finding the optimal task schedule. The approach is applied to a flow network as a case study, but can be applied to systems of different nature. Keywords Scheduling · Discrete event simulation · Process automation · Automata theory · Tropical automata Mathematics Subject Classification 68R05
Communicated by Rosana Sueli da Motta Jafelice. * Jose Aguilar [email protected] Karla Quintero [email protected] Eric Niel eric.niel@insa‑lyon.fr Laurent Pietrac laurent.pietrac@insa‑lyon.fr 1
Institut National Des Sciences Appliquées de Lyon, Villeurbanne, France
2
CEMISID, Universidad de Los Andes, La Hechicera, Mérida, Venezuela
3
GIDITIC, Universidad EAFIT, Medellín, Colombia
123 Vol.:(0123456789)
K. Quintero et al.
1 Introduction The problem studied in this work is about a system with limited resources, and numerous tasks to be executed at the earliest. In the following, the terms ‘task’ and ‘operation’ will be used indistinctly. The general context of application of our approach is when it is necessary on finding dates for the utilization of shared resources considering different constraints, such as unavailability (for example, due to the operations of transfer or corrective maintenance), financial, among others. This is a problem that can follow an allocation approach, where the synchronization, and improvement of operational and financial aspects, among others, must be simultaneously considered. The peculiarity in these problems is the multiple conflicts (due to the shared resources), and the necessity of the synchronization of tasks and of the integration of different sources of information (e.g., infrastructure topology, maintenance operations, information on planning, and management as the service agreements with the customers, etc.). Here, the decision-making is meant to be multivariate, it implies information about the availability of resources/devices, about the customers (e.g., their order of arrival), the maintenance plans, and the operational conditions (e.g., delays in service), to define an appropriate exploitation of the operational
Data Loading...
