Two-level priority scheduling framework in a max-plus linear representation
A common type of scheduling policy includes first-in-first-out (FIFO) and earliest-outset bases. Among many approaches to this, max-plus linear representation is beneficial for event-driven discrete event systems (DESs). The earliest event occurrence times can be represented by linear relations in m...
Main Authors: | , , |
---|---|
Format: | Article |
Language: | English |
Published: |
Taylor & Francis Group
2021-06-01
|
Series: | SICE Journal of Control, Measurement, and System Integration |
Subjects: | |
Online Access: | http://dx.doi.org/10.1080/18824889.2021.1894886 |
_version_ | 1797661110793404416 |
---|---|
author | Kyohei Sagawa Yoichi Shimakawa Hiroyuki Goto |
author_facet | Kyohei Sagawa Yoichi Shimakawa Hiroyuki Goto |
author_sort | Kyohei Sagawa |
collection | DOAJ |
description | A common type of scheduling policy includes first-in-first-out (FIFO) and earliest-outset bases. Among many approaches to this, max-plus linear representation is beneficial for event-driven discrete event systems (DESs). The earliest event occurrence times can be represented by linear relations in max-plus algebra, the resultant of which is analogous with the state equation in modern control theory. Methodologies in control theory such as evolution prediction and just-in-time scheduling can thus be utilized. Although useful, the description capability remains confined to FIFO contexts, for which the method would not be capable of producing an efficient solution for systems with two-level priorities. An entity, e.g. a task or token in scheduling contexts, with higher qualification would be prioritized over one with a lower qualification. A framework for overtaking tasks is necessary for this. Motivated by this need, this article is concerned with constructing a two-level priority scheduling methodology in a max-plus linear context. A numerical experiment applied to a simple manufacturing system highlights the significance of the constructed method. |
first_indexed | 2024-03-11T18:39:43Z |
format | Article |
id | doaj.art-518aa729cc994765aa3df630b348a33a |
institution | Directory Open Access Journal |
issn | 1884-9970 |
language | English |
last_indexed | 2024-03-11T18:39:43Z |
publishDate | 2021-06-01 |
publisher | Taylor & Francis Group |
record_format | Article |
series | SICE Journal of Control, Measurement, and System Integration |
spelling | doaj.art-518aa729cc994765aa3df630b348a33a2023-10-12T13:36:25ZengTaylor & Francis GroupSICE Journal of Control, Measurement, and System Integration1884-99702021-06-011429710310.1080/18824889.2021.18948861894886Two-level priority scheduling framework in a max-plus linear representationKyohei Sagawa0Yoichi Shimakawa1Hiroyuki Goto2Department of Information and Management Systems Engineering, Nagaoka University of TechnologyDepartment of Computer Science and Technology, Salesian PolytechnicDepartment of Industrial & Systems Engineering, Hosei UniversityA common type of scheduling policy includes first-in-first-out (FIFO) and earliest-outset bases. Among many approaches to this, max-plus linear representation is beneficial for event-driven discrete event systems (DESs). The earliest event occurrence times can be represented by linear relations in max-plus algebra, the resultant of which is analogous with the state equation in modern control theory. Methodologies in control theory such as evolution prediction and just-in-time scheduling can thus be utilized. Although useful, the description capability remains confined to FIFO contexts, for which the method would not be capable of producing an efficient solution for systems with two-level priorities. An entity, e.g. a task or token in scheduling contexts, with higher qualification would be prioritized over one with a lower qualification. A framework for overtaking tasks is necessary for this. Motivated by this need, this article is concerned with constructing a two-level priority scheduling methodology in a max-plus linear context. A numerical experiment applied to a simple manufacturing system highlights the significance of the constructed method.http://dx.doi.org/10.1080/18824889.2021.1894886max-plus linearstate equationfirst-in first-outtwo-level priority schedulingprioritization |
spellingShingle | Kyohei Sagawa Yoichi Shimakawa Hiroyuki Goto Two-level priority scheduling framework in a max-plus linear representation SICE Journal of Control, Measurement, and System Integration max-plus linear state equation first-in first-out two-level priority scheduling prioritization |
title | Two-level priority scheduling framework in a max-plus linear representation |
title_full | Two-level priority scheduling framework in a max-plus linear representation |
title_fullStr | Two-level priority scheduling framework in a max-plus linear representation |
title_full_unstemmed | Two-level priority scheduling framework in a max-plus linear representation |
title_short | Two-level priority scheduling framework in a max-plus linear representation |
title_sort | two level priority scheduling framework in a max plus linear representation |
topic | max-plus linear state equation first-in first-out two-level priority scheduling prioritization |
url | http://dx.doi.org/10.1080/18824889.2021.1894886 |
work_keys_str_mv | AT kyoheisagawa twolevelpriorityschedulingframeworkinamaxpluslinearrepresentation AT yoichishimakawa twolevelpriorityschedulingframeworkinamaxpluslinearrepresentation AT hiroyukigoto twolevelpriorityschedulingframeworkinamaxpluslinearrepresentation |