Scheduling Job Streams on Uniprocessors with Cold Start Delays
Notice bibliographique
Résumé
We consider uniprocessor job scheduling where jobs have deadlines and each job belongs to a job family. Each job family has an associated setup time or cold start delay, and when a job is scheduled, if the predecessor job does not belong to the same job family then this setup time needs to be included. We examine the scheduling problem when the objective is to minimize the number of tardy jobs, and the challenge of including the setup time for switching between job families results in poor performance of well-known policies such as earliest deadline first (EDF). We propose a near-optimal online scheduling policy for jobs with deadlines, on uniprocessor platforms. This problem arises in a variety of contexts including serverless computing and MLaaS (machine learning as a service) where a job request may need a suitable resource container to be provisioned if an earlier request was not of the same type. The general offline problem of job scheduling with job families and setup costs has previously been studied and shown to be NP-Hard. In an effort to improve our understanding of the online problem with the objective of maximizing the number of jobs that meet their deadlines, we focus on the case where all jobs have the same execution time. We show that even this special case is NP-Hard in the offline setting. The policy we propose, which requires job buffering, is nearly 1-competitive when each job has a reasonably large slack. We also propose a heuristic that performs well in many situations despite a weak competitive ratio.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction machine sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Le volet Gemma est une étiquette directe du modèle pour chaque travail de la base, lue sur la notice réduite au titre. Le volet Codex est un classifieur appris des 10 348 étiquettes directes de Codex et calibré sur les taux pondérés de l'échantillon; les champs sans appui suffisant ne portent aucun appel Codex. Le mode candidate est l'union des deux volets; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont pas des étiquettes humaines.
Scores du classifieur distillé par catégorie (deux têtes)
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,002 | 0,004 |
| Méta-épidémiologie (sens strict) | 0,001 | 0,001 |
| Méta-épidémiologie (sens large) | 0,002 | 0,001 |
| Bibliométrie | 0,001 | 0,001 |
| Études des sciences et des technologies | 0,001 | 0,001 |
| Communication savante | 0,002 | 0,002 |
| Science ouverte | 0,002 | 0,001 |
| Intégrité de la recherche | 0,001 | 0,001 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,003 | 0,001 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule source (Gemma direct ou Codex distillé), pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».