Minimal Total Weighted Tardiness in Tight-Tardy Single Machine Preemptive Idling-Free Scheduling
| Autor: | Vadim V. Romanuke |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
remaining available period
Mathematical optimization 021103 operations research Computer science Tardiness total weighted tardiness 0211 other engineering and technologies remaining processing period 02 engineering and technology General Medicine job preemptions boolean linear programming model Scheduling (computing) relative gap QA76.75-76.765 Boolean linear programming model 0202 electrical engineering electronic engineering information engineering heuristic 020201 artificial intelligence & image processing Computer software job scheduling single machine scheduling |
| Zdroj: | Applied Computer Systems, Vol 24, Iss 2, Pp 150-160 (2019) |
| ISSN: | 2255-8691 |
| Popis: | Two possibilities of obtaining the minimal total weighted tardiness in tight-tardy single machine preemptive idling-free scheduling are studied. The Boolean linear programming model, which allows obtaining the exactly minimal tardiness, becomes too time-consuming as either the number of jobs or numbers of job parts increase. Therefore, a heuristic based on remaining available and processing periods is used instead. The heuristic schedules 2 jobs always with the minimal tardiness. In scheduling 3 to 7 jobs, the risk of missing the minimal tardiness is just 1.5 % to 3.2 %. It is expected that scheduling 12 and more jobs has at the most the same risk or even lower. In scheduling 10 jobs without a timeout, the heuristic is almost 1 million times faster than the exact model. The exact model is still applicable for scheduling 3 to 5 jobs, where the averaged computation time varies from 0.1 s to 1.02 s. However, the maximal computation time for 6 jobs is close to 1 minute. Further increment of jobs may delay obtaining the minimal tardiness at least for a few minutes, but 7 jobs still can be scheduled at worst for 7 minutes. When scheduling 8 jobs and more, the exact model should be substituted with the heuristic. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|