============================================================================ Notes from Nenad Jovanovic Reading group 12/8/00 Notes: We continued working on the following problem: A set of jobs, all of them of the same length of 2 units, with given integer arrival times and integer deadlines, are given to be processed on a single processor. This is the offline problem i.e. all of the information is given upfront. Jobs can be scheduled with or w/o preemption. Objective is to find the max # of serviced jobs. Michael pointed out that he believes there is a strong relationship with a car painting problem. w/r to car painting there are 3 obj. functions proposed 1. approx. min # of color changes 2. approx. the savings due to reordering 3. approx max # of consecutive same color car pairs create a graph by making an edge joining cars i, j if i and j are of the same color and there is no other car of the same color between them. References: work of Goldwasser, Yap Michael reads email: open problem: identical length jobs, no preemption, deterministic offline. Q: Is it still open? There are deterministic 2-approx and randomized 4/3-approx. Note (John, Steve) If window sizes ( arrival to deadline) are identical we can solve the problem optimally by sorting. Q: If there is a const. # of window sizes can we solve it optimally by dynamic programming? Steve: Schedule all the jobs and no interval contains another interval so we can totaly order them. (?) After Joe proposed and retracted LP formulation of the problem an idea about using semi-definite programming resurfaced. Q: If we solve this sched. problem optimally would it give us 2-approx for the car paint. problem? Steve proposed incremental strategy given that there is a solution to the cars processed so far. John: Is there 1 - 1 corespondence between our sched. problem and max indep. set problem? We sketched some counter examples for FATF (FIrst Arrival TIme First) and EDD (Earliest Due Date) protocols. Steve: What is the highest approx ratio? Can we approx up to the additive const.? No! We can join many small but bad examples. Steve revisited Pinwheel Scheduling Problem: You have to schedule the monitoring of a number of concurrent processes with given minimum monitoring frequencies. Each monitoring step takes 1 time unit. Result: If the monitoring load factor is <0.81 you can allways do it optimally. At the end Steve brought Stock Ticker Protocol Design Problem. You want to display stock prices weighted by their popularity or importance and keep the alphabetical order preserved. ============================================================================ PPS--Here are the notes from two weeks ago. ============================================================================ Some notes on Scheduling, Reading group, Friday 12/01 ----------------------------------------------------- Prepared by Vinhthuy Phan ------------------------- We looked at a particular scheduling problem: - each job is of length 2 (it takes 2 units of time to get finished). - each job i has an arrival time a_i and deadline d_i There are a few variations of the problem: - 1 vs many CPUs - online vs offline - jobs are of length 1 and 2. If all jobs are of length 1, then the optimal solution can be found easily using greedy: carry out the job as soon as it arrives. - preemptive vs non-preemptive Steve and Michael thought that the non-preemptive version is more interesting combinatorially. Steve: if all jobs are of length 1, a way to find an optimal solution is to place the jobs in one side, units of time on the other. Form en edge in some way according to the arrival times and deadlines so that a maximal matching gives a feasible optimal solution. Question: how to extend to jobs of length 2? There are different objectives; ours current one is to execute the as many jobs as possible. ------------------------- Some people who have worked on this problem are Sally Goldman, Michael Goldwasser, and Chu Yap. ------------------------- Johnathan's online (works for offline too) algorithm (preemptive version): do the earliest deadline first if a new job comes with an early deadline, preempt to do this job. Michael, Estie: doesn't quite work. Ex: jobs A,B,C have deadlines at 6, job D has deadline at 5. A,B,C,D arrive one unit apart. 0 1 2 3 4 5 6 [ ]----------------| A [ ]------------| B [ ]--------| C [ | D the optimal schedule is (A,B,C); but the algorithm preempts A to do B, B to do C, C to do D -- at this point we can only do 2 jobs. ------------------------- To fix this, we should not start D. Adding D to the set of "active jobs" produces a non-feasible set of active jobs because we will have 4 units of works but only 3 units of time left. Pavel's proposal is to maintain an invariant to make sure that the set of active jobs is always feasible/schedulable whenever start a new job/add it to the set of active jobs. The invariant condition is: for all subset S of { active jobs }, units of work of S < units of time left with respect to S In our above example, when we look at D, the active set contains 3 units of of work each from A,B,C. There are only 3 units of time left. So D shouldn't be started. The set S consists of length-1 jobs. So units of work of S = |S|. Units of time left wrt S is max_{deadlines in S} - current_time This invariant can be relaxed not to include all subsets S {active jobs}, but only those necessary: all subsets with deadline <= i for current_time <= i <= max deadline of {active jobs}. These deadlines are linear-ordered, so we could do this by going from left to right. Bottom line: as I understand it, preemptive scheduling of length-2 jobs can be done in polynomial time. Barry, others: this can be polynomially extended to length-k jobs, based on the same idea. ------------------------- Estie: length-2 non-preemptive scheduling can be proved NPC by reducing to 3-partitioning problem. ------------------------- Michael: the reason to introduce this problem is because it is related to our car-painting problem. -------------------------