Need help with approach: Job Scheduling problem

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
2	maomao90	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Given N processes with Arrival times and Processing times, calculate and print minimum number of CPUs required if maximum allowed Turnaround time for each process is 10 units.

Turnaround time = Waiting time in queue + Processing time

Each processor has its own processing queue. Processes cannot be preempted.

Maximum number of CPUs allowed is 5. If more than 5 required, then print -1.

Example:

Task Arrival_time Processing_time
T1   2            7
T2   3            5

Ans: 2

I was thinking of a greedy approach initially (which turned out to be wrong) based on the following observations (which might be wrong)

A process which with earlier arrival time should always get scheduled earlier than a process with later arrival time — no benefit in scheduling it later
It is always better to schedule a process on a CPU with longer queue (as long as the Turnaround time condition is met), reason being, we will have a free resource available earlier, i.e. tightest fit match — Eg: [Arrival time, Processing time] If we have CPU1 queue to be [0,2][2,5] and CPU2 [0,3], if a job [3,4] comes in, schedule it on CPU1. We will have a free resource (CPU2) — available earlier — i.e. from 3 onwards, but if we schedule on CPU2, then we only have free resource (CPU1) from 5 onwards.

Approach:

- At each arrival time, sort jobs based on Processing time.
- Maintain a decreasing load list of CPUs (i.e. CPU with highest load is first on the list)
- Allocate jobs to CPUs in the given order, highest processing time job to first possible busiest CPU, reorder CPUs if necessary after allocating, if cannot allocate to existing CPUs, create new CPU (if <= 5) and allocate job to it

Though this might work well in an online setting (i.e. when we don't know the all the jobs and times in advance), it is suboptimal when we know that information. Eg:

Task Arrival_time Processing_time
T1   0            3
T2   0            3
T3   3            8

The approach outlined would schedule T1 and T2 on CPU1, and when T3 arrives, it gets scheduled on CPU2 (which gets created). If we'd known that we would need CPU2, we could've as well scheduled T2 on CPU1, which is better.

Hence, I realized that I may not be utilizing the <=5 CPU part of the question. Now I think the approach should be to try a solution with 1 CPU first, if not possible, then with 2 CPUs,.. Now for each arrival time, sort jobs in ascending order of processing time and allocate it in that order to the free-est CPU — i.e. least turnaround time — from amongst the k CPUs where k = 1 to begin with, 2 if solution with k=1 is not possible and so on.

If this too is wrong, what could be the right approach to this problem?

History