Sequenciamento em filas de servidor único.users.isr.ist.utl.pt/~cfb/MSc5-  · Sequenciamento em filas…

  • Published on
    06-Nov-2018

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

  • Sequenciamento em filas de servidor nico.Variante da regra c.

    Zita Daniela Batista Fernandes

    Dissertao para obteno do Grau de Mestre em

    Engenharia Electrotcnica e de Computadores

    JriPresidente: Doutor Francisco Miguel Prazeres Silva Garcia

    Orientador: Doutor Carlos Filipe Gomes Bispo

    Doutor Joo Manuel Freitas Xavier

    Doutor Carlos Baptista Cardeira

    Outubro de 2007

  • Abstract

    The goal of the work described in this thesis concerns the presentation of arguments that bring a new

    perspective to some existing results of queuing networks. Comparison between numerical data obtained

    with models that use only buffer length as state variable with models that use also server state show

    that the models which only use buffer length do not correctly represent the systems under study. Also a

    new scheduling policy is presented. It is motivated by the belief that the marginal cost of waiting should

    not be a constant and by the belief that strict priorities are only interesting to customers having higher

    priority. With this new policy we propose to replace strict priorities, as is the case of the crule. The

    variance of the cycle time for all classes achieved with the new policy will be presented, as is numerically

    computed. The tools used to get the results presented in this work, such as Dynamic Programming and

    Discrete Event Simulation, are also described.

    Keywords

    Queuing Networks, Scheduling Problem, Queuing Networks Modeling, State Costs, Variance of Waiting

    Time.

    i

  • ii

  • Resumo

    O objectivo do trabalho descrito nesta dissertao prende-se com a apresentao de argumentos que

    do uma nova perspectiva a alguns resultados clssicos da teoria das filas de espera. A comparao

    entre dados numricos obtidos com modelos que fazem uso apenas do nmero de clientes no sistema

    como variveis de estado e com modelos que tambm usam o estado dos servidores mostra que os

    modelos que apenas usam o nmero de clientes no representam os sistema em estudo de forma

    correcta.

    Tambm se apresenta uma nova poltica de sequenciamento. Esta motivada pela crena de que o

    custo marginal de esperar no deveria ser constante e pela crena de que as prioridades estritas, como

    forma de gerir filas de espera, so interessantes apenas para os clientes que pertenam classe mais

    prioritria. Com esta nova poltica prope-se substituir prioridades estritas, como o caso da regra c.

    A varincia do tempo de ciclo para todas as classes que se obtm com a nova poltica apresentada,

    atravs de exemplos numricos.

    Os instrumentos utilizados para obteno dos resultados apresentados ao longo da dissertao,

    como sejam a Programao Dinmica e a Simulao de Sistemas Dinmicos de Eventos Discretos,

    so tambm descritos.

    Palavras-Chave

    Redes de Filas de Espera, Polticas de Sequenciamento, Modelao de Redes de Filas de Espera,

    Custos de Estado, Varincia do Tempo de Ciclo.

    iii

  • iv

  • Contedo

    1 Introduo 1

    1.1 Estrutura da dissertao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

    2 Enquadramento 5

    2.1 Redes de Filas de Espera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

    2.1.1 Modelos de Filas de Espera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

    2.1.2 Modelos para as Chegadas e Processamentos . . . . . . . . . . . . . . . . . . . . 6

    2.1.3 Parmetros Estruturais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

    2.1.4 Polticas de Operao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

    2.1.5 Estabilidade das Redes de Filas de Espera . . . . . . . . . . . . . . . . . . . . . . 9

    2.1.6 Sequenciamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

    2.2 Cadeias de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

    2.2.1 Cadeias de Markov em Tempo Discreto e Estado Discreto . . . . . . . . . . . . . . 12

    2.2.2 Cadeias de Markov em Tempo Contnuo e Estado Discreto . . . . . . . . . . . . . 13

    2.2.3 Uniformizao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

    2.2.4 Problemas de Deciso de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

    2.3 Programao Dinmica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

    2.3.1 Formulao de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

    2.3.2 O Algoritmo de Programao Dinmica . . . . . . . . . . . . . . . . . . . . . . . . 21

    2.3.3 Problema de Horizonte Infinito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

    2.3.4 Iterao de Valor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

    3 Formulao de Problemas 25

    3.1 Modelao usando 1 Varivel VS 2 Variveis . . . . . . . . . . . . . . . . . . . . . . . . . 25

    3.1.1 Modelao usando 1 varivel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

    3.1.2 Modelao usando 2 variveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

    3.1.3 Comparao dos Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

    3.2 A -Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

    v

  • 4 Simulao 37

    4.1 Caractersticas Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

    4.2 Modelao da Rede . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

    4.3 Dinmica da Rede . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

    4.4 Especificao das Polticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

    4.5 Arquitectura do Simulador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

    4.6 Recolha de Informao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

    5 Resultados 45

    5.1 Modelao usando 1 Varivel VS 2 Variveis . . . . . . . . . . . . . . . . . . . . . . . . . 45

    5.1.1 Programao dinmica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

    5.1.2 Simulao da c-rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

    5.1.3 Comparao de Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

    5.2 A Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

    5.2.1 Resultados da PD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

    5.2.2 Formulao Intuitiva da Poltica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

    5.2.3 Varincia do Tempo de ciclo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

    5.2.4 Varincia Global e Dependncia dos Processos . . . . . . . . . . . . . . . . . . . 55

    6 Concluses e Desenvolvimentos Futuros 57

    6.1 Desenvolvimentos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

    A Unified Modelling Language do simulador. 61

    vi

  • Lista de Figuras

    2.1 Exemplo de uma rede de filas de espera com um servidor e uma classe de clientes. . . . 5

    2.2 Rede de filas de espera com trs classes de clientes. . . . . . . . . . . . . . . . . . . . . 8

    2.3 Sequenciamento de trs classes de clientes para um servidor. . . . . . . . . . . . . . . . 9

    2.4 Exemplo de controlo de sequenciamento aplicado a uma rede com duas classes de clientes. 11

    3.1 Rede de filas de espera com um servidor e duas classes de clientes. . . . . . . . . . . . 26

    3.2 Diagramas de transio de estado em tempo contnuo. . . . . . . . . . . . . . . . . . . . 27

    3.3 Diagramas de transio de estado uniformizados. . . . . . . . . . . . . . . . . . . . . . . 28

    3.4 Diagrama de Transies do modelo de duas variveis em tempo contnuo. . . . . . . . . 29

    3.5 Diagrama de Transies do modelo de duas variveis uniformizado. . . . . . . . . . . . . 30

    3.6 Matriz de deciso da c-rule e transies possveis. . . . . . . . . . . . . . . . . . . . . . 32

    4.1 Rede de filas de espera. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

    4.2 UML. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

    4.3 Interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

    4.4 Tabela de output do simulador. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

    5.1 Custo de estados iniciais do espao de estados. . . . . . . . . . . . . . . . . . . . . . . . 46

    5.2 Custo de estados centrais do espao de estados. . . . . . . . . . . . . . . . . . . . . . . 47

    5.3 Ficheiro de entrada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

    5.4 Rede de filas de espera virtual criada na simulao. . . . . . . . . . . . . . . . . . . . . . 48

    5.5 Intervalo de confiana a 95% para estados inciais do espao de estados. . . . . . . . . . 48

    5.6 Intervalo de confiana a 95% para estados inciais do espao de estados. . . . . . . . . . 49

    5.7 Sobreposio dos custos obtidos por PD no intervalo de confiana. . . . . . . . . . . . . 49

    5.8 Sobreposio dos custos obtidos por PD no intervalo de confiana. . . . . . . . . . . . . 49

    5.9 Matrizes de deciso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

    5.10 Matriz de deciso genrica da rule. . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

    5.11 Matrizes de deciso