Genetic algorithm fitness function for scheduling

Question

For Job shop scheduling, I built a fitness function:

def makespan_timeCalculation(lot_size, RHS, setup_time, processing_time, sequence, mc_op): 
 machine_assigne_time =[[0 for i in range(mc_op[k])] for k in range(len(mc_op))]
 max_c = [0 for i in range(len(lot_size))] # Equal number of job
 completion_time = [0 for i in range(len(RHS))] 
 # Check all indices of RHS (Step 2 + 3 + 6)
 for r in range(len(RHS)):
 procTime = run_time(r, lot_size, RHS, sequence, processing_time) + setup_time[RHS[r][2]]
 if lot_size[RHS[r][0]][RHS[r][1]] > 0: # Lot size not zero (Step 4)
 if (machine_assigne_time[RHS[r][2]][RHS[r][3]] == 0 and RHS[r][2] == sequence[RHS[r][0]][0]):
 # Step 5.1: First assignment to machine m and operation equal first operation in sequence
 completion_time[r] = setup_time[RHS[r][2]] + procTime
 machine_assigne_time[RHS[r][2]][RHS[r][3]] +=1
 elif (machine_assigne_time[RHS[r][2]][RHS[r][3]] == 0 and RHS[r][2] != sequence[RHS[r][0]][0]):
 # Step 5.2: First assignment to machine m and operation over first operation in sequence
 curent_sequence_index = sequence[RHS[r][0]].index(RHS[r][2]) # Calculate index sequence of current chromosome
 prev_sequence = sequence[RHS[r][0]][curent_sequence_index-1] # Return previous sequence operation of current chromosome
 prev_operation_comp_index = [i[0:3] for i in RHS].index([RHS[r][0], RHS[r][1], prev_sequence]) # Return previous chromosome of current job + sublot
 completion_time[r] = max(setup_time[RHS[r][2]], completion_time[prev_operation_comp_index]) + procTime
 machine_assigne_time[RHS[r][2]][RHS[r][3]] +=1
 #print(curent_sequence_index, RHS[r]) 
 elif (machine_assigne_time[RHS[r][2]][RHS[r][3]] > 0 and RHS[r][2] == sequence[RHS[r][0]][0]):
 # Step 5.3: First operation in sequence and machine m assignment > 1 (dung de xem xet khi co su khac nhau giua setup time ban dau, va setup time doi part) 
 prev_op_mc_RHS_index = max([i for i, al in enumerate(RHS[:r]) if RHS[r][2:] == al[2:]])
 completion_time[r] = completion_time[prev_op_mc_RHS_index] + procTime
 machine_assigne_time[RHS[r][2]][RHS[r][3]] +=1
 elif (machine_assigne_time[RHS[r][2]][RHS[r][3]] > 0 and RHS[r][2] != sequence[RHS[r][0]][0]):
 # Step 5.4 Operation over first operation in sequence and machine m assignment > 1
 curent_sequence_index = sequence[RHS[r][0]].index(RHS[r][2]) # Calculate index sequence of current chromosome
 prev_sequence = sequence[RHS[r][0]][curent_sequence_index-1] # Return previous sequence operation of current chromosome
 prev_operation_comp_index = [i[0:3] for i in RHS].index([RHS[r][0], RHS[r][1], prev_sequence]) # Return previous chromosome of current job + sublot 
 prev_op_mc_RHS_index = max([i for i, al in enumerate(RHS[:r]) if RHS[r][2:] == al[2:]]) 
 completion_time[r] = max(completion_time[prev_operation_comp_index], completion_time[prev_op_mc_RHS_index]) + procTime
 machine_assigne_time[RHS[r][2]][RHS[r][3]] +=1
 max_c[RHS[r][0]] = max(max_c[RHS[r][0]], completion_time[r])
 return max(max_c)

The result is fine but speed is very slow. Could you help to have a look and advise on improvement?

• Toby Speight: Welcome to Code Review! The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. Also, you don't need to mention the language - that information is in the tags.
• Graipher: Could you add some example input? Specifically, it is unclear what exactly RHS, lot_size, etc look like (are they nested dictionaries/lists?).
• user119557: Please don't use paste.ofcode.org for code. The snippets expire after a week, which means the link would be useless. Add the code directly into the question

Answer 1

I think the biggest boost to readability will come from giving things proper names. You currently have a lot of RHS[r][i] going on, with i = 0, 1, 2, 3. For someone who does not know what these things are (including possibly you in a few months), this makes the code basically unreadable.

I would start by making the iteration look like this:

for r, (a, b, c, d) in enumerate(RHS):
 ...

Where a, b, c, d are actual sensible names (like name, length, or whatever is actually at those positions).

Next, your setup code can be simplified using the fact that e.g. [0] * 3 == [0, 0, 0] (but don't do it with nested loops, see below):

machine_assigne_time = [[0] * op] for op in mc_op]
max_c = [0] * len(lot_size) # Equal number of job
completion_time = [0] * len(RHS)

And finally, without being able to run your code, the most obvious case for the slow down are your repeated calls to list.index. This is very slow (\$\mathcal{O}(n)\$ in the worst case). I would try to find a more efficient data structure for this (dictionaries?).

• Khái Duy: Hi Graipher, kindly check my data structure per parameter as edited above. Could you advise the way how to re-structure it?
• Khái Duy: Kindly check link I have problem when running many times in row 142, 144. Can you help to advise also?