مقاله انگلیسی رایگان در مورد سیستم های بحرانی مختلط – الزویر 2019

 

مشخصات مقاله
ترجمه عنوان مقاله برنامه ریزی با زمان پردازش نامعلوم در سیستم های بحرانی مختلط
عنوان انگلیسی مقاله Scheduling with uncertain processing times in mixed-criticality systems
انتشار مقاله سال 2019
تعداد صفحات مقاله انگلیسی 17 صفحه
هزینه دانلود مقاله انگلیسی رایگان میباشد.
پایگاه داده نشریه الزویر
نوع نگارش مقاله
مقاله پژوهشی (Research Article)
مقاله بیس این مقاله بیس میباشد
نمایه (index) Scopus – Master Journals List – JCR
نوع مقاله ISI
فرمت مقاله انگلیسی  PDF
ایمپکت فاکتور(IF)
4.712 در سال 2018
شاخص H_index 226 در سال 2019
شاخص SJR 2.205 در سال 2018
شناسه ISSN 0377-2217
شاخص Quartile (چارک) Q1 در سال 2018
مدل مفهومی ندارد
پرسشنامه ندارد
متغیر دارد
رفرنس دارد
رشته های مرتبط مهندسی برق
گرایش های مرتبط مهندسی کنترل
نوع ارائه مقاله
ژورنال
مجله / کنفرانس مجله اروپایی درباره تحقیقات عملیاتی – European Journal of Operational Research
دانشگاه  Department of Control Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, Czech Republic
کلمات کلیدی برنامه ریزی، بحرانی مختلط، زمان پردازش نامعلوم، شعبه و قیمت
کلمات کلیدی انگلیسی Scheduling، Mixed-criticality، Uncertain processing time، Branch-and-price
شناسه دیجیتال – doi
https://doi.org/10.1016/j.ejor.2019.05.038
کد محصول  E13514
وضعیت ترجمه مقاله  ترجمه آماده این مقاله موجود نمیباشد. میتوانید از طریق دکمه پایین سفارش دهید.
دانلود رایگان مقاله دانلود رایگان مقاله انگلیسی
سفارش ترجمه این مقاله سفارش ترجمه این مقاله

 

فهرست مطالب مقاله:
Abstract
1. Introduction
2. Uncertainty and execution model
3. Problem with two criticality levels
4. Problem with three criticality levels
5. Computational experiments
6. Conclusion
Acknowledgment
Appendix A
References

 

بخشی از متن مقاله:
Abstract

Many scheduling problems that can be identified inside safety-critical applications, such as in autonomous cars, tend to be mixed-critical. Such scheduling problems consider tasks to have different criticalities depending on the safety levels (activation of brakes vs. activation of air-conditioning). The biggest challenge in those scheduling problems arises from the uncertainty of processing times as it disturbs the predictability of the system and thus makes the certification of the system difficult. To overcome this uncertainty, we model the tasks to have multiple processing times concerning their criticality. This approach converts these scheduling problems into a deterministic scheduling with alternative processing times. Here, we study an N P-hard single machine scheduling problem with makespan minimization, where the non-preemptive tasks can have multiple processing times. To solve the problem, we propose an approximation algorithm, a novel mixed-integer linear programming block formulation, and an efficient exact branch-and-price decomposition for two criticality levels. Furthermore, we demonstrate that the optimal schedules are represented as trees, which enables to formulate an exact algorithm for the problem with three criticality levels. The efficiency of the proposed method is demonstrated for difficult problem instances with up to 1000 tasks. The experimental evaluation demonstrates that our algorithms have improved the results of the best-known method by nearly two orders of magnitude.

Introduction

This paper addresses scheduling in mixed-criticality systems where tasks have different degrees of importance (criticalities) and share a common resource. The key requirement of these systems is to isolate tasks such that a lower-criticality task does not influence any higher-criticality task. When the processing time of tasks is uncertain, the unexpected prolongation of a task may affect the execution of another task with higher criticality, which is extremely dangerous for safety-critical systems. A naive solution assuming the worst-case processing times leads to inefficient utilization of the resource. This is problematic, especially for embedded systems having limited computational and hardware resources. To overcome the processing time uncertainty, we utilize the so-called F-shaped tasks, where each task has an integer criticality and a set of alternative processing times. The schedules with F-shaped tasks are proactive and contain exponentially many alternative schedules, with the alternative being selected based on the realized processing time of a task that occurs during the runtime execution of the schedule. The structure of the schedule guarantees that in any of these alternatives, all highly critical tasks are performed, rejecting low-criticality tasks only if a more critical one is prolonged. At the same time, the resource is efficiently utilized since when critical tasks are not prolonged, low-criticality tasks may use the resource. Therefore, the proactive schedules with Fshaped tasks achieve a trade-off between the required safety margins and an efficient resource usage. An important advantage of this approach is that despite such flexibility, the schedules only take polynomial-sized space. In addition, even though the corresponding optimization problem is N P-hard, our exact algorithms are computationally efficient in practice.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا