Job (task) scheduling is one of the oldest problems in mathematics, operations research, and computer science research. Basically, given a set of tasks under various constraints (required execution time, deadline, precedence among tasks, and so on), an execution sequence is to be determined. The objective may be for as many jobs to meet the deadlines as possible, or it may be to minimize the total execution time. Many of these job scheduling problems belong to a class of problems called the NP-complete problem.

This paper studies the scheduling of generalized multiframe tasks (GMF). A task consists of multiple frames to be executed. Each frame has a different deadline. Think of this as a video-playing task. Each task is a set of frames to be displayed. The frames have sequential relations. This paper adds parameter adaptation to this problem (called GMF-PA), that is, it “permits a flexible selection of frame relative deadline and minimum separation time for each frame under earliest deadline first [EDF] scheduling.”

A scheduling algorithm is proposed and proved to be “a necessary schedulability test in general.” When parameters are integers, it also proves “that the algorithm is a sufficient and necessary schedulability test, i.e., an exact test.” Because of intractability, the paper also develops an approximation algorithm. “The speed-up factor of [the] approximation algorithm is 1 + ε with respect to the exact schedulability test of GMF-PA tasks under EDF scheduling,” where ε is any small real number. A few other related problems are also studied.

It’s a very long paper (30 pages). Most pages contain mathematical equations and proofs. I believe that the reviewers of the original paper would have had a hard time checking its correctness. However, the important part is the algorithm proposed. If the algorithm can be applied and gets results, it is useful.