As the hardware and software using parallel processors are developed, the technique for using these facilities in real world has been requested. Task scheduling is needed to use processors efficiently for these systems. When many users want to get serviced by a system, the scheduling algorithm of it should maximize overall degree of satisfaction of users. This thesis conserns scheduling algorithms for this kind of aim.
In such a system, scheduling algorithm should minimize flow time which is the sum of completion time of tasks, since flow time counts every tasks' response time and each user wants to get serviced as soon as possible. Furthermore, the concept of rejection is used in this thesis. When the system must execute so many tasks that the load of the system is very high, the execution speed of all tasks may be slow down. If the system rejects some tasks paying penalties for rejecting them, remaining tasks can be executed in reasonable speed.
So, we consider the scheduling problems where tasks can be rejected. The measure for scheduling algorithm in this thesis is the sum of penalties of rejected tasks and flow time of executed tasks. The goal of scheduling algorithm is to minimize this measure. This thesis deals two different problems. First, we consider the problem where the release times of tasks are the same. We develope algorithm when scheduling uses one processor, and then generalize it to the case that scheduling uses arbitrary number of processors. The problem where tasks have precedence constraint is also considered. Second, we consider the problem where release times of tasks are different and preemption is allowed.
For the first problem, we develope algorithm whose time complexity is $O(n^2)$ and $O(n^3)$ for the case with and without precedence constraint each. For the second problem, we show that the case where a tasks is preempted at most once can be solved using the same algorithm.
