A generalized c-mu rule for scheduling multiclass queueing systems with dependent arrival rates

Purpose: A service discipline chooses the order in which the customers are served at each station. Examples of service disciplines are the first in first out (FIFO) and last in first out (LIFO), they are the most popular and probably the most intuitive disciplines. Jobs among all classes are ranked according to the arrival time at the queue. When we are dealing with several classes with different arrival rates the whole procedure could become very hard. For this reason static buffer priority disciplines are sometimes preferred. All the classes at each station have a fixed ranking, the higher the ranking the higher the priority. The cμ rule is one of these disciplines, it ranks the classes according to the holding cost and the service rate. The goal of this thesis is to determine the reasons why the cμ rule is not always able to predict the optimal policy that minimizes the total cost when the arrival rates are dependent on the job in service. We started to address the simplest system with only two classes of products/clients, then we moved to a more general n-class problem. We wanted to determine a new formula able to predict the right scheduling sequence with the new set of parameters (dependent arrival rates were added). We applied then the new rule to a real case to test its effectiveness. Knowledge background: The cμ rule was introduced for the first time in 1961 in the paper "Queues" written by D.R. Cox and Walker Smith [1]. The cμ rule defines the optimal scheduling sequence for different classes in the system. The priority level is determined by taking the product of the service rate and the holding cost rate for a given class. The larger the product the higher the priority level. In the following years there were several papers and studies on this topic with different assumptions and parameters used in the model. So far nobody considered the case where the arrival rates were dependent on the product class in service. Research Questions: Raaijmakers [2] showed that for some sets of parameters the cμ rule is not able to predict the optimal policy so to minimize the total costs. We moved from this point looking for an explanation of the strange behavior and possibly a solution. Design/Methodology/Approach: The thesis is divided in two main parts, the first one is purely theoretical while the second one is the application to a real case of the theoretical results. In the theoretical part we run the the fluid model optimization problem several times changing the parameters. The results obtained with the fluid model were compared with the Markov decision process formulation of the problem. Both the methods showed the same conclusions. After the definition of a new relationship for the optimal scheduling thanks to the fluid model and the MDP, we proved it analytically. In the real case application we run a big number of simulations (fixed time increment type) to see the goodness of the new rule applied to the hospital emergency room process. Main Finding: The main result achieved is the proposal of a new rule able to minimize the total holding cost when scheduling the production of several product/client classes having different priority level. The rule was defined firstly for a simple two-class system and later it was extended to the general n-class system. Pratical Implementations: It is possible to apply the new rule to systems/processes in which the arrival rates are dependent on the product/class in service such as hospital emergency rooms and postal offices. Limitations and future developments: The main limitations of the new rule are the followings: the arrival rates of products/clients depend on what is in service at that time. We considered only the holding cost and we neglect other type of cost such as set up cost and penalties due to non completion of the jobs. We did not consider all the possible parameters, it could be interesting to include the abandon rate in the model. After a certain time spent in the queue the client can decided to abandon the system. For these reasons could be interesting to analyze the effects of these parameters on the rule we obtained and possibly to define even a more general one.

Obiettivo: La disciplina di servizio determina l’ordine con cui i prodotti sono proces- sati ad ogni stazione. Alcuni esempi di discipline sono dati da first in first out (FIFO) e last in first out (LIFO), esse sono probabilmente le più conosciute. I prodotti di tutte le classi sono classificati in base all’istante temporale in cui sono entrati nella rispettiva coda. Quando il sistema è caratterizzato da molte classi con diversi tassi di arrivo il pro- cesso di classificazione può diventare molto complesso. Per questa ragione a volte vengono preferite politiche di static buffer priority. Tutti i prodotti di una singola classe sono descritti da un rango costante, più il rango è alto più il livello di priorità è elevato. La cμ rule rientra in questa categoria di politiche e ordina le classi basandosi sul costo di attesa in coda e il tasso di processamento. Lo scopo di questo studio è di determinare le ragioni per cui la cμ rule non è sempre in grado di suggerire la politica ottimale per minimizzare il costo totale del sistema quando i tassi di arrivo dipendono dalla classe sotto processo al momento dell’arrivo in coda. Abbiamo iniziato affrontando il caso più semplice con sole due classi di prodotti/clienti diversi, da qui siamo poi passati al caso generale con n classi diverse. Un ulteriore obiettivo è la definizione di una nuova relazione che permetta di determinare la politica ottimale con i nuovi parametri aggiunti. Infine abbiamo l’obiettivo di applicare questa nuova regola a un caso reale per testarne la sua bontà. Background letterario:La cμ rule è stata introdotta per la prima volta nel 1961 nell’articolo scientifico, poi diventato libro, "Queues" da D.R. Cox e Walter Smith [1]. La cμ rule definisce la sequenza di schedulazione ottimale per diverse classi di prodotto all’interno di un sistema. Il livello di priorità è definito come il prodotto tra il tasso di processa- mento e il costo di attesa in coda di una classe di prodotti. Più il risultato è grande più il livello di priorità è elevato. Negli anni successivi sono stati condotti diversi studi su questo argomento introducendo diversi parametri e ipotesi nel sistema sotto esame. Ad oggi nessuno ha mai considerato il caso in cui i tassi di arrivo dipendono dalla classe in servizio al momento dell’arrivo in coda. Domande di ricerca: Raaijmakers [2] ha mostrato che per alcune combinazioni di parametri la cμ rule non è in grado di suggerire la politica ottimale per minimizzare i costi. Queste osservazioni sono il punto di partenza del nostro studio. Design/Metodologia/Approccio:Lo studio è diviso in due parti distinte. La prima parte è prettamente teorica mentre la seconda consiste nell’applicazione au un reale caso reale pratico dei risultati teorici ottenuti. Nella parte teorica abbiamo eseguito svari- ate volte il problema di ottimizzazione basato sull’approssimazione Fluid model del sis- tema cambiando di volta in volta i parametri in ingresso. I risultati ottenuti sono stati confrontati con la formulazione del Markov Decision Process del problema. Entrambi i metodi hanno restituito risultati concordanti. Da questi risultati abbiamo ricavato una nuova relazione per lo scheduling ottimo e infine abbiamo dimostrato analiticamente la sua validità. Il caso reale trattato è la gestione dei differenti codici di gravità e il loro smis- tamento all’interno di un Pronto Soccorso. Abbiamo simulato le dinamiche del Pronto Soccorso attraverso una simulazione a tempi fissi, l’obiettivo era di testare la bontà della regola formulata. Risultati Principali: Il principale risultato di questa tesi è la definizione di una nuova regola per la valutazione dei livelli di priorità per diverse classi di prodotti/clienti. La regola è stata definita inizialmente per il solo caso semplice con due classi e successivamente è stata estesa al caso generale con n classi. Implicazioni Pratiche:E’ possibile applicare i risultati di questo studio a numerosi casi pratici in cui i tassi di arrivo dipendono dalla classe/prodotto in servizio come nel caso di uffici postali o Pronto soccorsi. Limitazioni e sviluppi futuri: Le principali limitazioni di questa nuova regola sono le seguenti: è necessario che il tasso di arrivo dei prodotti/clienti dipenda dal tipo di prodotto-cliente sotto processo al momento dell’arrivo in coda. Il modello inoltre considera solamente il costo di permanenza in coda del singolo prodotto, abbiamo trascurato altri tipi di costo come il costo di set up e penalties dovute al mancato completamento del prodotto. Non abbiamo considerato tutti i possibili parametri, può essere utile infatti includere nel modello la possibilità da parte del cliente di abbandonare il sistema dopo un certo lasso di tempo passato in coda. Per queste ragioni sarebbe interessante studiare gli effetti che questi parametri hanno sulla regola da noi ricavata e possibilmente, in futuro, determinarne una di carattere ancor più generale.