Loading...

Job Scheduling in a Single Machine with Ability to Run Jobs in Parallel

Mashayekh, Khadijeh | 2014

1040 Viewed
  1. Type of Document: M.Sc. Thesis
  2. Language: Farsi
  3. Document No: 47911 (19)
  4. University: Sharif University of Technology
  5. Department: Computer Engineering
  6. Advisor(s): Abam, Mohammad Ali
  7. Abstract:
  8. This thesis introduces and investigates a new kind of scheduling model, in which the total amount of computational resources to be allocated at each moment by the processor is constrained and upper bounded by a constant. The time for a task to be executed is also dependent on the computational resources, dedicated to it by the processor, assuming that the multiplication of the execution time by the dedicated computational resources is a constant for each job. We investigate various objective functions, such as minimizing the number of tardy jobs, minimizing maximum latency and etc, under varying constraints. The investigated objective functions are: a) Minimize number of tardy jobs b) Minimize total tardiness c) Minimize makespane d) Minimize maximum latency e) Minimize total finish time. We will investigate two version of the problem, the one where preemption is allowed, and the one without preemption. For the first type with objective functions “a” to “e” we propose a method to reduce the problem to state of the art scheduling problems, where preemption is allowed. For the second type with objective functions “a”, “b”, “d” and “e” we show NP-hardness and we propose a method to reduce the objective function “c” in this category to it’s well known and state of the art version, and show that such reductions are not possible for the four other mentioned objective functions in this category. In the end an approximation algorithm with constant with approximation ratio of 12 is proposed for the objective function “b”, under the condition that the all instances to be scheduled are of equal area , in the second category, with a running time of O(n lg n)
  9. Keywords:
  10. Scheduling ; Parallel Processing ; Approximate Algorithm ; NP-Hard Problems ; Calculation Power

 Digital Object List

 Bookmark