Abstract
Scheduling tasks in overloaded real-time systems is a challenging problem that has received a significant amount of attention in recent years. The processor is overloaded with more tasks than its capacity, resulting in missed deadlines and degraded system performance. Therefore, scheduling algorithms play a critical role in ensuring that high-priority tasks are completed on time while minimizing the impact of incomplete lower-priority tasks. This paper proposes an efficient Weighted Partial MaxSAT(WPMS) encoding that returns an optimal solution in which the total weight of incomplete tasks is minimized in a single machine environment. To assess the efficiency of our proposed formulation, a comparative analysis is conducted alongside the state-of-the-art encoding. By examining the solving 75 distinct problems, it becomes evident that the WPMS encoding proposed herein exhibits a considerable advantage in terms of both time and memory efficiency.
Disclosure statement
No potential conflict of interest was reported by the author(s).
Additional information
Notes on contributors
Mohammad Mehdi Pourhashem Kallehbasti
Mohammad Mehdi Pourhashem Kallehbasti is an assistant professor at the University of Science and Technology of Mazandaran, Behshahr. His research interests are in software engineering, formal methods, and artificial intelligence.
Jamshid Pirgazi
Jamshid Pirgazi is an assistant professor at the University of Science and Technology of Mazandaran, Behshahr. His research interests are in bioinformatic and machine learning.
Ali Ghanbari Sorkhi
Ali Ghanbari Sorkhi is an assistant professor at the University of Science and Technology of Mazandaran, Behshahr. His research interests are in image processing and deep learning.
Ali Kermani
Ali Kermani is an assistant professor at the University of Science and Technology of Mazandaran, Behshahr. His research interests are in image processing and pattern recognition.