Distributed scheduling based on multi-agent system: a swarm approach for collaborative optimization

Funder

Organizational Unit

Publications

Capacitated waste collection problem solution using an open-source tool

Publication . Silva, Adriano S.; Alves, Filipe; Díaz de Tuesta, Jose Luis; Rocha, Ana Maria A.C.; Pereira, Ana I.; Silva, Adrián; Gomes, Helder

Population in cities is growing worldwide, which puts the systems that offer basic services to citizens under pressure. Among these systems, the Municipal Solid Waste Management System (MSWMS) is also affected. Waste collection and transportation is the first task in an MSWMS, carried out traditionally in most cases. This approach leads to inefficient resource and time expense since routes are prescheduled or defined upon drivers’ choices. The waste collection is recognized as an NP-hard problem that can be modeled as a Capacitated Waste Collection Problem (CWCP). Despite the good quality of works currently available in the literature, the execution time of algorithms is often forgotten, and faster algorithms are required to increase the feasibility of the solutions found. In this paper, we show the performance of the open-source Google OR-Tools to solve the CWCP in Bragança, Portugal (inland city). The three metaheuristics available in this tool were able to reduce significantly the cost associated with waste collection in less than 2 s of execution time. The result obtained in this work proves the applicability of the OR-Tools to be explored for waste collection problems considering bigger systems. Furthermore, the fast response can be useful for developing new platforms for dynamic vehicle routing problems that represent scenarios closer to the real one. We anticipate the proven efficacy of OR-Tools to solve CWCP as the starting point of developments toward applying optimization algorithms to solve real and dynamic problems.

2023Journal article

Open access

Conceptual multi-agent system design for distributed scheduling systems

Publication . Alves, Filipe; Rocha, Ana Maria A.C.; Pereira, Ana I.; Leitão, Paulo

With the progressive increase in the complexity of dynamic environments, systems require an evolutionary configuration and optimization to meet the increased demand. In this sense, any change in the conditions of systems or products may require distributed scheduling and resource allocation of more elementary services. Centralized approaches might fall into bottleneck issues, becoming complex to adapt, especially in case of unexpected events. Thus, Multi-agent systems (MAS) can extract their automatic and autonomous behaviour to enhance the task effort distribution and support the scheduling decision-making. On the other hand, MAS is able to obtain quick solutions, through cooperation and smart control by agents, empowered by their coordination and interoperability. By leveraging an architecture that benefits of a collaboration with distributed artificial intelligence, it is proposed an approach based on a conceptual MAS design that allows distributed and intelligent management to promote technological innovation in basic concepts of society for more sustainable in everyday applications for domains with emerging needs, such as, manufacturing and healthcare scheduling systems.

2023Book part

Open access

Using OR-Tools When Solving the Nurse Scheduling Problem

Publication . Oliveira, Márcia; Rocha, Ana Maria A.C.; Alves, Filipe

Scheduling of employees is a common problem that can be found in most organizations all over the world. One example is the nurse scheduling problem (NSP), which is a complex combinatorial opti-mization problem faced by healthcare institutions in assigning working and nonworking days. The NSP comprises constraints for the nurses, for the hospital and considers specific labor regulations, aswell as the skills and preferences ofworkers. In summary, it involves hard and soft constraints. It is essential to create a quality timetable that can lead to a more contented and thus,more effec-tive and productiveworkforce. To improve this process, it can be used automated approaches and techniques. In this study, a litera-ture review about the nurse scheduling problem and how to use the Google OR-Tools software to solve it is performed. Moreover, an example of an NSP involving 10 nurses being assigned to three shifts a day, seven days a week is presented. Some condi-tions/constraints have been added in order to reproduce a real situation.

2024Conference paper

Restricted access

Multi-agent system architecture for distributed home health care information systems

Publication . Alves, Filipe; Rocha, Ana Maria A.C.; Pereira, Ana I.; Leitão, Paulo

In recent years, the aging population has increased. The intervention of Home Health Care (HHC) has been an asset, however, needs technological innovation for the high level of complexity and requirements. Innovation in the HHC system is crucial since management still occurs manually using classical methods, usually centralized and static. The mapping of real HHC problems, enables an application model of a distributed intelligent system, considering the operational planning needs, promoting a digital and sustainable ecosystem. This work aims to specify a flexible architecture for routing and scheduling tasks in distributed HHC. It considers multi-agent systems technology to guarantee the fast response to condition changes in existing planning, merged with optimization algorithms that allow achieving optimal solutions. Collaboratively, the information digitalization for real-time monitoring will coordinate a socialized solution using different tools and techniques, ensuring robustness and responsiveness in a domain with emerging needs. © 2021, IFIP International Federation for Information Processing.

2021Conference paper

Open access

A hybrid approach to operational planning in home health care

Publication . Alves, Filipe; Duarte, António; Rocha, Ana Maria A.C.; Pereira, Ana I.; Leitão, Paulo

Home health care (HHC) management needs to plan their operations to synchronize professionals and allocate resources to perform several HHC services needed by patients. The growing demand for this type of service dictates the interest of all the stakeholders (professionalsand patients) in finding high-quality daily solutions and logistics. Routing and scheduling are problems of combinatorial nature, extremely complex, and require sophisticated optimization approaches. This work aims to contribute to cost-efficient decision-making in the general improvement of the service quality. Thus, a mixed integer linear programming model, a genetic algorithm, and a hybrid approach were used to solve the operational planning through test instances of different sizes for public home care providers. Computational results are presented, followed by a discussion on the advantages and shortcomings, highlighting the strength of each approach.

2023Conference paper

Open access