CS298 Proposal
ASH - A Scheduler for HOAs
Qian Li (sabrinaqq2002@yahoo.com)
Advisor: Dr. Chris Pollett
Committee Members: Dr. Sami Khuri (khuri@cs.sjsu.edu) Dr. David Taylor (taylor@cs.sjsu.edu).
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
Week 1-2:
Jan 26-Feb 5 | Implement our variant of the semi-clairvoyant algorithm. |
Week 3- 4:
Feb 6-19 | Research job constraints involved in typical real-life HOAs, Add
configurable parameters into the scheduling algorithm |
Week 5-6:
Feb 20- Mar 5 | Develop the configurable and applicable scheduling algorithm. |
Week 7-8:
Mar 6 -19 | Implement and test the scheduler by applying the developed
algorithm. |
Week 9:
Mar 20-26 | Improve the scheduler. |
Week 10-11:
Mar 27- Apr 9 | Finalize the scheduler. |
Week 12 -13:
Apr 10 -23 | Start writing the report and submit draft to the committee. |
Week 14-15:
Apr 24- May 7 | Finalize the report and prepare oral presentation. |
Week 16-18:
May 8-25 | Oral defense. |
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
|