Scheduling in a single-server with state-dependent service rates
| Autor: | Balakrishna Prabhu, Rhonda Righter, Urtzi Ayesta |
|---|---|
| Přispěvatelé: | Réseaux, Mobiles, Embarqués, Sans fil, Satellites (IRIT-RMESS), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Équipe Services et Architectures pour Réseaux Avancés (LAAS-SARA), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Centre National de la Recherche Scientifique (CNRS), Lawrence Berkeley National Laboratory [Berkeley] (LBNL), Centre National de la Recherche Scientifique - CNRS (FRANCE), IKERBASQUE (SPAIN), Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), University of California - UC Berkeley (USA), University of the Basque Country - UPV/EHU (SPAIN), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Statistics and Probability
Mathematical optimization Computer science Holding cost Système d'exploitation Réseaux et télécommunications 020206 networking & telecommunications 02 engineering and technology Single server queue [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Management Science and Operations Research Operations research 01 natural sciences Systèmes embarqués Industrial and Manufacturing Engineering Scheduling (computing) 010104 statistics & probability Idle [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] Queueing theory State dependent Architectures Matérielles 0202 electrical engineering electronic engineering information engineering 0101 mathematics Statistics Probability and Uncertainty |
| Zdroj: | Probability in the Engineering and Informational Sciences Probability in the Engineering and Informational Sciences, Cambridge University Press (CUP), 2020, 34 (4), pp.507-521. ⟨10.1017/S0269964819000160⟩ Probability in the Engineering and Informational Sciences, 2020, 34 (4), pp.507-521. ⟨10.1017/S0269964819000160⟩ |
| ISSN: | 0269-9648 1469-8951 |
| DOI: | 10.1017/S0269964819000160⟩ |
| Popis: | International audience; We consider single-server scheduling to minimize holding costs where the capacity, or rate of service, depends on the number of jobs in the system, and job sizes become known upon arrival. In general, this is a hard problem, and counter-intuitive behavior can occur. For example, even with linear holding costs the optimal policy may be something other than SRPT or LRPT, it may idle, and it may depend on the arrival rate. We first establish an equivalence between our problem of deciding which jobs to serve when completed jobs immediately leave, and a problem in which we have the option to hold on to completed jobs and can choose when to release them, and in which we always serve jobs according to SRPT. We thus reduce the problem to determining the release times of completed jobs. For the clearing, or transient system, where all jobs are present at time 0, we give a complete characterization of the optimal policy and show that it is fully determined by the cost-to-capacity ratio. With arrivals, the problem is much more complicated, and we can obtain only partial results. We show that if the cost-to-capacity ratio is linear, then all non-idling policies yield the same average cost. We further characterize the optimal policy in some special cases. For example, we show that as long as capacity is increasing in the number of jobs, LRPT stochastically minimizes the mean busy period. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|