Single-Machine Preemptive Scheduling with Release Dates Involving the Total Weighted Late Work Criterion

This paper investigates the preemptive scheduling with release dates on a single machine to minimize the total weighted late work.We firstly present an O(nlogn)-time algorithm for the single-agent problem with disagreeable weights and due dates.And then,we extendedly study the two-agent Pareto-scheduling problem with jobs having a common due date to minimize each agent's total weighted late work,and give a polynomial-time algorithm that is based on the parameters analysis to generate the Pareto frontier.

Chronically Evaluated Highest Instantaneous Priority Next: A Novel Algorithm for Processor Scheduling

This paper proposes a novel chronically evaluated highest instantaneous priority next processor scheduling algorithm. The currently existing algorithms like first come first serve, shortest job first, round-robin, shortest remaining time first, highest response ratio next and varying response ratio priority algorithm have some problems associated with them. Some of them can lead to endless waiting or starvation and some of them like round-robin has problem of too many context switches and high waiting time associated with them. In the proposed algorithm, we have taken care of all such problems. As the novel algorithm is capable of achieving as good results as shortest remaining time first algorithm and also it will never lead to starvation.

Preemptive Semi-online Algorithms for Parallel Machine Scheduling with Known Total Size

This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi-online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi-online algorithm is at least （2m-3）/（m-1） for any m〉2 and present optimal semi-online algorithms for m = 2, 3.

Optimal Preemptive Online Algorithms for Scheduling with Known Largest Size on Two Uniform Machines

In this paper, we consider the seml-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time （starting from time zero） when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ [1, ∞）, and show that idle time is required to achieve the optimality during the assignment procedure of the algorithm for any s 〉 （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）. The competitive ratio of the algorithms is （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）, which matches the randomized lower bound for every s ≥ 1. Hence randomization does not help for the discussed preemptive scheduling problem.

Semi-Online Algorithms for Scheduling with Machine Cost

In this paper, we consider the following semi-online List Model problem with known total size. We are given a sequence of independent jobs with positive sizes, which must be assigned to be processed on machines. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. By normalizing all job sizes and machine cost, we assume that the cost of purchasing one machine is 1. We further know the total size of all jobs in advance. The objective is to minimize the sum of the makespan and the number of machines to be purchased. Both non-preemptive and preemptive versions are considered. For the non-preemptive version, we present a new lower bound 6/5 which improves the known lower bound 1.161. For the preemptive version, we present an optimal semi-online algorithm with a competitive ratio of 1 in the case that the total size is not greater than 4, and an algorithm with a competitive ratio of 5/4 otherwise, while a lower bound 1.0957 is also presented for general case.

Quantitative analysis of real-time performance and hardware requirements for edge computing platform

For real-time edge systems such as autonomous driving,not only the correctness of task functions,but also the response and processing time of tasks should be satisfied.In the hardware selection phase of a real-time system,time series analyses must be performed on the hardware platform running real-time applications.At present,the common method of worst-case execution time(WCET)analysis focuses mainly on analyzing the impact of hardware platform architecture or task execution process on the task running time.However,different tasks in an autopilot system have different levels of urgency,and preemption between tasks is the main factor that affects the task execution time.The key problem is how to quantify the time fluctuation caused by task preemption for each subtask of the autopilot system running on a fixed hardware platform.This paper presents a time analysis method for a real-time application based on a queuing theory and preemptive scheduling strategy,which assigns different priorities to tasks according to their time urgency and preemptive scheduling according to task priority.Through an experimental case study,the impact of the running time of each subtask in a real-time application with task priority preemptive scheduling is analyzed,along with the impact of changes in hardware platform performance on such real-time applications.