مقاله انگلیسی رایگان در مورد سیستم های بحرانی مختلط – الزویر ۲۰۱۹
مشخصات مقاله | |
ترجمه عنوان مقاله | برنامه ریزی با زمان پردازش نامعلوم در سیستم های بحرانی مختلط |
عنوان انگلیسی مقاله | Scheduling with uncertain processing times in mixed-criticality systems |
انتشار | مقاله سال ۲۰۱۹ |
تعداد صفحات مقاله انگلیسی | ۱۷ صفحه |
هزینه | دانلود مقاله انگلیسی رایگان میباشد. |
پایگاه داده | نشریه الزویر |
نوع نگارش مقاله |
مقاله پژوهشی (Research Article) |
مقاله بیس | این مقاله بیس میباشد |
نمایه (index) | Scopus – Master Journals List – JCR |
نوع مقاله | ISI |
فرمت مقاله انگلیسی | |
ایمپکت فاکتور(IF) |
۴٫۷۱۲ در سال ۲۰۱۸ |
شاخص H_index | ۲۲۶ در سال ۲۰۱۹ |
شاخص SJR | ۲٫۲۰۵ در سال ۲۰۱۸ |
شناسه ISSN | ۰۳۷۷-۲۲۱۷ |
شاخص Quartile (چارک) | Q1 در سال ۲۰۱۸ |
مدل مفهومی | ندارد |
پرسشنامه | ندارد |
متغیر | دارد |
رفرنس | دارد |
رشته های مرتبط | مهندسی برق |
گرایش های مرتبط | مهندسی کنترل |
نوع ارائه مقاله |
ژورنال |
مجله / کنفرانس | مجله اروپایی درباره تحقیقات عملیاتی – 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 ۱٫ Introduction ۲٫ Uncertainty and execution model ۳٫ Problem with two criticality levels ۴٫ Problem with three criticality levels ۵٫ Computational experiments ۶٫ 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. |