Hello, I've got a problem that I can't seem to figure out. I'm writing a program to simulate a process manager, and I'm doing four different algorithms: First come first serve, shortest job next, shortest remaining time, and round robin. I've got the first two down perfect, but I'm having trouble with shortest remaining time.

So I've got two lists:
arrive=[0,3,6,7,7,10,15,16]
exe=[12,3,11,1,4,5,20,7]

"arrive" is the arrival time of a job and "exe" is the execution duration. I can only process one job at a time, and for this algorithm the processor is allocated to the job closest to completion (as long as it has arrived).

So, for example, in my lists, a job arrives at time 0 with a duration of 12. Now, I would only process it for 3 times through because the next job arrives at 3 and it has a shorter execution duration.

Hopefully that makes sense. Basically I just need help setting something up. I've been adding the arrived items to their own list, with their execution duration in another. I can post my code for the other algorithms if it would help anyone. I could also post any code for this algorithm that I've attempted. Thanks!!!!

Is this logic correct?
arrive=[0, 3, 6, 7, 7, 10, 15, 16]
exe= [12, 3, 11, 1, 4, 5, 20, 7]

The first piece arrives at 0 and takes 12 units to complete, so if we add completion time, we have
arrive=[0]
exe=[12]
completion=[12]

arrive=[0, 3]
exe=[12, 3]
completion=[12, 6]
The second piece arrives at 3, and takes 3 units to complete=completes at 6. Since it's completion time is less than the first piece, work is done on it. So at the completion of the second piece, that is at "6", we have for this first piece:
arrive=[6] ## time now
exe=[9] ## units left --> 12-3
completion=[15]
etc.

So you would use a function to compute completion whenever a piece is added, or when one piece completes and take the lowest completion time?

Yes, your logic seems to be correct. As for the completion list, I would want to compute it whenever a piece is added. I'll be back online in a few with some code...I went ahead and finished the fourth algorithm today since I already had it worked out on paper. I think I can get it working...it's just one of those things I have to wrap my brain around and scribble out pseudo code. Thanks for the help so far, it's giving me some new ideas!

Alright, so remember "arrive" and "exe" are my two main lists. "arrived" is the list for jobs that have arrived, and "waitToExe" is the list for waiting job's execution duration. "msCount" is to count time (fake milliseconds).

``````def SRT(arrive,exe,arrived,waitToExe,msCount):
tempArrived=[]
tempWaitToExe=[]
while arrived == []:
a=0
#print "Time: ",msCount,"ms"
while a < len(arrive): #match an arrival time for the current msCount
if arrive[a] == msCount:
arrived.append(arrive[a])
waitToExe.append(exe[a])
a+=1
msCount+=1
while sum(waitToExe) != 0: #while the sum of waiting's execution duration is NOT zero...
#print "----------------------------" #this was commented out since it's looping
#print arrived
#print waitToExe
#print "----------------------------"
n=0
while n<len(waitToExe): #for length of waiting...
sortWaitToExe = sorted(waitToExe) #sort to get smallest job duration
if waitToExe[n] == sortWaitToExe[0] and waitToExe[n]!=0: #if current item = the lowest item in the sorted list
print "Processing item! Time: ",msCount #"process"
print arrived
print waitToExe
waitToExe[n] = waitToExe[n]-1 #subtract one "ms" from waiting duration
sortWaitToExe[0] = sortWaitToExe[n]-1 #subtract one "ms" from first sorted item
a=0
while a < len(arrive):  #then check again if any new jobs have arrived....
if arrive[a] == msCount:
tempArrived.append(arrive[a])
tempWaitToExe.append(exe[a])
a+=1
for item in tempWaitToExe:  #if an item in temp list is larger than an item in the real list, then break loop
if item<sortWaitToExe[0]:
n=len(waitToExe)
n+=1
for item in tempArrived:
for item2 in tempWaitToExe:
waitToExe.append(item2) #same...
tempArrived=[] #clear temp list
tempWaitToExe=[]#same``````

Anyway, this works fine until it finishes the second job and for some reason it croaks.

Oops, ignore line 26...I'm really tired.

It appears that the problem is here
while sum(waitToExe) != 0: #while the sum of waiting's execution duration is NOT zero...

You subtract from waitToExe, but not until it reaches zero. It appears that you only subtract once for each "n".

``````while n<len(waitToExe): #for length of waiting...
sortWaitToExe = sorted(waitToExe) #sort to get smallest job duration
if waitToExe[n] == sortWaitToExe[0] and waitToExe[n]!=0: #if current item = the lowest item in the sorted list
print "Processing item! Time: ",msCount #"process"
print arrived
print waitToExe
waitToExe[n] = waitToExe[n]-1 #subtract one "ms" from waiting duration``````

Also, you do not return arrived or waitToExe from the function, so they should be returned or should just be defined by the function. I would suggest using a few functions instead on one long block of code to pinpoint the errors to a small function.

Thanks a lot for the help...I'll clean it up and see if I can it working. I'll post back soon.

This appears to work, but is still rough and just a proof of concept. It adds the unit to a dictionary as it's arrive time is reached, so that any finished units can be deleted from the dictionary as well. So a unit is processed until it is finished or until the next arrive time is reached. At the end the remaining units are processed in the order received but can be sorted and processed in any other order. The toughest part of this is to break it into small enough pieces that can be easily coded.

``````import datetime
import time

""" Results Should Be The Following:
arrive=[0,3,6,7,7,10,15,16]
exe=[12,3,11,1,4,5,20,7]

Num  Process   Time     Time
Time   Remaining   Now
0       3        9        3
1       3        0        6  #1 Finished
0       1        8        7
3       1        0        8  #3 Finished
4       2        2       10
4       2        0       12  #4 Finished
5                5
5       3        2       15
5       1        1
"""

class ProcessUnit:
def __init__(self, arrive, exe):
unit_to_process = {}
ctr = 0
unit_number = 0
time_now = 0
next_start_time = 0
stop = len(arrive) - 2

## add first unit to start the process
ctr += 1
if ctr > 500:     ## limit to 500 cycles

print "\n", "-"*60

## add next unit to the dictionary ?
print unit_to_process

##  initialize stop time = next start time - time now
##            print "initialize stop time", arrive[add_ctr+1], time_now
if stop_time < 0:      ## two units arrive at same time
stop_time = 99999

##  find smallest completion time and compare to
##  the current stop time (next arrive time)
smallest = 99999
for key in unit_to_process:
##               print "time remaining", unit_to_process[key][1], stop_time
if unit_to_process[key][1] < smallest:
smallest = unit_to_process[key][1]
unit_number = key   # process smallest unit no matter how long the time is

if smallest < stop_time:
stop_time = smallest

print "processing next unit, stop_time", stop_time, "unit number", unit_number
self.process_unit(stop_time)
time_now += stop_time
unit_to_process[unit_number][0] += stop_time
unit_to_process[unit_number][1] -= stop_time

##  if completed, delete from dictionary
if unit_to_process[unit_number][1] < 1:
print "dictionary delete key", unit_number
del unit_to_process[unit_number]

print "\n-------- processing remaining units ----------------"
print unit_to_process, "\n"

units = unit_to_process.keys()
units.sort()
for key in units:
print "unit =", key, "  time =", unit_to_process[key][1]
self.process_unit(unit_to_process[key][1])

def process_unit(self, time_to_process):
print "     ",
for n in range(0, time_to_process):
time.sleep(1.0)
print n,
print

##===================================================================
arrive=[0,3,6,7,7,10,15,16]
exe=[12,3,11,1,4,5,20,7]

start_time = datetime.datetime.now()
P = ProcessUnit(arrive, exe)
print "\n", datetime.datetime.now() - start_time``````

there is an error in the last SJF

## add last unit and process remaining in order received print "\n-------- processing remaining units ----------------"
in this step the error