An LP-Based Algorithm for Scheduling Preemptive and/or Non-Preemptive Real-Time Tasks
We consider a real-time system that requires the time stimuli to the system are processed through sequences of tasks to be within specified upper bounds, where the set of tasks can be the mixture of preemptive and non-preemptive tasks, and we propose an algorithm to design a static priority scheduli...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
The Japan Society of Mechanical Engineers
2010-06-01
|
| Series: | Journal of Advanced Mechanical Design, Systems, and Manufacturing |
| Subjects: | |
| Online Access: | https://www.jstage.jst.go.jp/article/jamdsm/4/3/4_3_578/_pdf/-char/en |
| _version_ | 1811291824914956288 |
|---|---|
| author | Hideki HASHIMOTO Mutsunori YAGIURA |
| author_facet | Hideki HASHIMOTO Mutsunori YAGIURA |
| author_sort | Hideki HASHIMOTO |
| collection | DOAJ |
| description | We consider a real-time system that requires the time stimuli to the system are processed through sequences of tasks to be within specified upper bounds, where the set of tasks can be the mixture of preemptive and non-preemptive tasks, and we propose an algorithm to design a static priority scheduling for the system. In the algorithm, local search is used to determine priorities of tasks, and whenever the priorities are fixed, the periods of tasks are determined. This subproblem can be described as a mathematical programming formulation and is solved via linear programming techniques. Finally, we report computational results for sample instances from a company. |
| first_indexed | 2024-04-13T04:35:57Z |
| format | Article |
| id | doaj.art-83c1003d4540458f8e7a22b2d3a95c39 |
| institution | Directory Open Access Journal |
| issn | 1881-3054 |
| language | English |
| last_indexed | 2024-04-13T04:35:57Z |
| publishDate | 2010-06-01 |
| publisher | The Japan Society of Mechanical Engineers |
| record_format | Article |
| series | Journal of Advanced Mechanical Design, Systems, and Manufacturing |
| spelling | doaj.art-83c1003d4540458f8e7a22b2d3a95c392022-12-22T03:02:10ZengThe Japan Society of Mechanical EngineersJournal of Advanced Mechanical Design, Systems, and Manufacturing1881-30542010-06-014357858710.1299/jamdsm.4.578jamdsmAn LP-Based Algorithm for Scheduling Preemptive and/or Non-Preemptive Real-Time TasksHideki HASHIMOTO0Mutsunori YAGIURA1Department of Industrial and Systems Engineering, Chuo UniversityGraduate School of Information Science, Nagoya UniversityWe consider a real-time system that requires the time stimuli to the system are processed through sequences of tasks to be within specified upper bounds, where the set of tasks can be the mixture of preemptive and non-preemptive tasks, and we propose an algorithm to design a static priority scheduling for the system. In the algorithm, local search is used to determine priorities of tasks, and whenever the priorities are fixed, the periods of tasks are determined. This subproblem can be described as a mathematical programming formulation and is solved via linear programming techniques. Finally, we report computational results for sample instances from a company.https://www.jstage.jst.go.jp/article/jamdsm/4/3/4_3_578/_pdf/-char/enreal-time systempreemptive and/or non-preemptive tasksstatic priority schedulinglinear programminglocal search |
| spellingShingle | Hideki HASHIMOTO Mutsunori YAGIURA An LP-Based Algorithm for Scheduling Preemptive and/or Non-Preemptive Real-Time Tasks Journal of Advanced Mechanical Design, Systems, and Manufacturing real-time system preemptive and/or non-preemptive tasks static priority scheduling linear programming local search |
| title | An LP-Based Algorithm for Scheduling Preemptive and/or Non-Preemptive Real-Time Tasks |
| title_full | An LP-Based Algorithm for Scheduling Preemptive and/or Non-Preemptive Real-Time Tasks |
| title_fullStr | An LP-Based Algorithm for Scheduling Preemptive and/or Non-Preemptive Real-Time Tasks |
| title_full_unstemmed | An LP-Based Algorithm for Scheduling Preemptive and/or Non-Preemptive Real-Time Tasks |
| title_short | An LP-Based Algorithm for Scheduling Preemptive and/or Non-Preemptive Real-Time Tasks |
| title_sort | lp based algorithm for scheduling preemptive and or non preemptive real time tasks |
| topic | real-time system preemptive and/or non-preemptive tasks static priority scheduling linear programming local search |
| url | https://www.jstage.jst.go.jp/article/jamdsm/4/3/4_3_578/_pdf/-char/en |
| work_keys_str_mv | AT hidekihashimoto anlpbasedalgorithmforschedulingpreemptiveandornonpreemptiverealtimetasks AT mutsunoriyagiura anlpbasedalgorithmforschedulingpreemptiveandornonpreemptiverealtimetasks AT hidekihashimoto lpbasedalgorithmforschedulingpreemptiveandornonpreemptiverealtimetasks AT mutsunoriyagiura lpbasedalgorithmforschedulingpreemptiveandornonpreemptiverealtimetasks |