Need help with approach: Job Scheduling problem

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

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