Abstract:

The scheduling problem has been a basic problem either in computer science research or in real application research. This is also a difficult research problem, and therefore most of the research in this field has incorporated with some potential inapplicable assumptions, for example assuming the processing time as unit time, assuming the releasing times are the same. Consequently, there does not exist a really applicable scheduling algorithm for real use. My project focus on developing an applicable job scheduler, which is capable of aiding the homeowners' associations in achieving an optimal scheduling results, not only to have customers' requests fulfilled in timely manner, but also to be given immediate feedback on a timeframe in which activities will be made. The ASH can collect the customers' requests and arrange the wait-for scheduling jobs in increasingly automatically generated job ID order. According to house-owner association's configuration data, such as current month budget limit, priority assignment, the ASH will start scheduling the jobs with ASH scheduling algorithm. The scheduling results will be shown in time stream with the costs and penalties (if it has) caused by passing the due dates. For performance analysis, it will also calculate the average flow time, average stretch and turnaround time for the final scheduling results.

CS297 Results

• Implemented the Greedy unit-time-job scheduling algorithm that can match as many deadlines as possible to minimize the penalties caused by passing the due date.
• Compared Semi-clairvoyant R algorithm, FIFO and SPTF with respect to their average flow time and average stretch, SPTF outstand from the other two. However, it has fatal flaw-long process time request job gets into starvation. Therefore, the Sc-R is the appropriate choice for HOA.
• Studied the probability, statistics and queueing theory, found out the embedded Markov chain is another good approach to HOA model.

Proposed Schedule

Key Deliverables:

• Software
  • Our scheduler, ASH, will collect the customers' requests and arrange the still to be scheduled jobs in increasing order. According to the homeowner association's configuration data, ASH will schedule jobs with ASH scheduling algorithm that we will develop based on combining semi-clairvoyant algorithm with some of the other algorithms we have studied.
  • The scheduling results will be displayable in our system as a time stream with the costs and penalties caused by passing the due dates. Also, our program will calculate the average flow time, average stretch and turnaround time for the final scheduling results.
  • We will run several tests on our scheduler and investigate how well the scheduler works by trying different jobs and analyzing the results.
• Report
  • Test results and Code documentation.
  • Final oral presentation report and writing report.

Innovations and Challenges

• As far as we can tell, there does not exist a useful, configurable scheduling program on the market for House Owner Associations, so ours would be a new product in this area.
• Applying Semi-Clairvoyant R algorithm in HOA is the first-time try; moreover we will try to improve it by combing other scheduling algorithms in order to get more efficient scheduling result.
• It will combine various scheduling algorithms such as Semi-Clairvoyant R and greedy algorithms, and some techniques in a novel way and in a new domain.

References:

[Al90] A. Allen. Probability, Statistics, and Queueing Theory with Computer Science Applications. Academic Press, inc. 1990.

[AL99] Online algorithm, Susanne Albers, Stefano Leonardi. Volume 31. Issue 3. (September 1999) Article No. 4, Year of Publication: 1999 ISSN:0360-0300

[AR98] A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press, 1998.

[ATCH] Algorithms and Theory of Computation Handbook, page 10-17, Copyright 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright 2000 CRC Press LLC.

[BLMP04] B. Luca, L. Stefano, M. Alberto, P. Kirk, Semi-clairvoyant scheduling. Theoretical Computer Science 324(2004) 325--335.

[CLR90] Thomas H. Cormen, Charles E.Leiserson, Ronald L. Rivest, Introduction to algorithms. MIT Press. 1990.

[MR95] M.Rajeev, R. Prabhakar, Randomized Algorithms, Cambridge University Press, 1995

[NG02] Nutt G. Operating Systems. A Modern Perspective 2nd Edition LAB UPDATE