Un approccio innovativo di Programmazione Lineare nei problemi di Schedulazione

Abstract

Leonhard Euler (1707-1783) diceva che nulla accade nel mondo senza un massimo o un minimo. L'ottimizzazione è un campo in cui l'obiettivo è quello di massimizzare i guadagni o minimizzare i costi. Pertanto, è essenziale utilizzare le risorse in modo saggio ed evitare gli sprechi, soprattutto considerando la sostenibilità o il tempo. Inoltre, l'ottimizzazione aiuta a risolvere i problemi quotidiani trovando le soluzioni migliori o quasi ottimali nel rispetto di determinati requisiti o vincoli. Per esempio, una sfida comune nelle scuole è la creazione di un orario fattibile e possibilmente ottimale per il semestre. Questo campo ha ampie applicazioni in discipline quantitative, tra cui l'economia, l'ingegneria e l'informatica. Questa tesi si concentra su un ramo dell'ottimizzazione: la schedulazione. Il concetto generale di programmazione può essere illustrato con l'esempio sopra citato. Si tratta dell'allocazione di risorse e attività nel tempo. Lo studio di quest'area dell'ottimizzazione è affascinante perché presenta un problema difficile e impegnativo, soprattutto per gli scenari su larga scala. Per semplificare la formulazione del modello di ottimizzazione, il problema di schedulazione in questa tesi è descritto come lavori schedulati su macchine su una o più istanze all'interno di un orizzonte temporale. Esaminando lo stato dell'arte, sono state identificate tre principali difficoltà nella schedulazione su larga scala: la formulazione del modello, la ricerca di una soluzione fattibile entro un limite di tempo e la visualizzazione della schedulazione. Per affrontare questi problemi viene introdotto un approccio innovativo che combina tre componenti: il task "Build and Solve" della piattaforma Rulex per facilitare la formulazione del problema, gli algoritmi Fast e Naive di Rulex per trovare rapidamente soluzioni fattibili e uno script Python per visualizzare la schedulazione.

Leonhard Euler (1707-1783) said that nothing happens in the world without some maximum or minimum. Optimization is the field in which the goal is to maximize gains or minimize costs. Therefore, it is essential to use resources wisely and avoid waste, especially considering sustainability or time. Moreover, optimization helps solve everyday problems by finding the best or near-optimal solutions while respecting certain requirements or constraints. For example, a common challenge in schools is creating a feasible and possibly optimal timetable for the semester. This field has broad applications in quantitative disciplines, including economics, engineering, and computer science. This thesis focuses on one branch of optimization: scheduling. The general concept of scheduling can be illustrated with the aforementioned example. It involves the allocation of resources and activities over time. Studying this area of optimization is fascinating because it presents a difficult and challenging problem, especially for large-scale scenarios. To simplify the formulation of the optimization model, the scheduling problem in this thesis is described as jobs scheduled on machines over one or more instances within a time horizon. Reviewing the state of the art, three major difficulties have been identified in large-scale scheduling: formulating the model, finding a feasible solution within a time limit, and visualizing the schedule. An innovative approach is introduced to address these issues and combines three components: the “Build and Solve” task on the Rulex Platform for easy problem formulation, Rulex’s Fast and Naive algorithms for quickly finding feasible solutions, and a Python script for visualizing the schedule. In optimization discussions, Machine Learning, particularly Support Vector Machines, plays a pivotal role, commonly employed for classification and regression tasks within this field.