A Least-Laxity-First Scheduling Algorithm of Variable Time Slice for Periodic Tasks

Introduction

There are many procedures and jobs with cyclical characteristics in the real world, as well as in the batch production of products. Every batch is a production cycle and there are many processes in the production cycle. For example, automobile manufacturing, production of milk, computer manufacturing, clothing making, and crops production all have cyclical characteristics. They all are composed of periodic tasks. The cycle of crops production is once or twice per year from sowing to harvesting and that of fruit production is once a year.

After analyzing the production process of these periodic tasks carefully, it is not difficult to find out the following common characteristics of them:

• •

  There exist parallel actions among processes. For example, parallelism occurs in an assembly line. The second process of the first product making action and the first process of the second product making action are in parallel. When one product is being assembled in a process, the other might be in the next process. In general, all of the batch productions are the same, which all are parallel actions.

• •

  The system with periodic tasks is not usually fully loaded. It might become idle in some intervals, such as the winter in agricultural production. All the batch productions have the same or similar property. Their differences are long or short in idle intervals.

• •

  Each task is independent and has possibly different production cycles.

• •

  There are not strict sequences among some processes.

If we extract the essential features and ignore the specific production procedure for every production task which has the periodic characteristics, we can discuss the production scheduling with the help of computer simulation. Production details of a task is not important for scheduling, but the start time of periodic task, the length of a cycle and the time of real production in a cycle are essential. In order to make full use of the production resources and make the greatest benefit, an efficient scheduling is necessary. Efficient scheduling schemes could use the least scheduling time and make a system to gain the most execution time. For instance, rural workers can take in hand more part time when his major task, i.e., crop production is idle. A production system could be used to take on other jobs in free times. This kind of scheduling is quite useful and can make an enterprise to gain more benefit. Hence, real-time task scheduling is an important topic. A computer simulation could give an exact solution for the production task scheduling in the real world.

Real-time task scheduling has been studied widely in computer science. Many scholars and experts have paid much attention to studying on the real-time task scheduling and they have achieved a lot of research results. The real-time scheduling is a fundamental problem of operating systems. When a computer is multi-programmed, it frequently has multiple processes competing for the CPU (Central Process Unit) at the same time. This situation occurs whenever two or more processes are simultaneously in the ready state. If only one CPU is available, a choice has to be made, i.e., which process runs first. The part of an operating system that makes the choice is called scheduler and the used algorithms is called scheduling algorithms. These topics form the subject matter of the process scheduling (Tanenbaum, 2002). The process is basically a program in execution. Then the real-time scheduling of tasks is very important. Scheduling is also a daily human cognitive activity, people need to think of the schedules everyday to make their work more efficient. It is a common problem in every field related with cognitive informatics (Wang, 2003, 2007; Ngolah, Wang, & Tan, 2004), such as, software development, knowledge management, natural intelligence and artificial intelligence.