2
\$\begingroup\$

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?

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 22, 2018 at 9:20
  • 1
    \$\begingroup\$ Could you add some example input? Specifically, it is unclear what exactly RHS, lot_size, etc look like (are they nested dictionaries/lists?). \$\endgroup\$ Commented Aug 22, 2018 at 9:40
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Sep 22, 2018 at 9:06

1 Answer 1

Reset to default
1
\$\begingroup\$

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?).

\$\endgroup\$
2
  • \$\begingroup\$ Hi Graipher, kindly check my data structure per parameter as edited above. Could you advise the way how to re-structure it? \$\endgroup\$ Commented Aug 23, 2018 at 2:39
  • \$\begingroup\$ Kindly check link I have problem when running many times in row 142, 144. Can you help to advise also? \$\endgroup\$ Commented Aug 23, 2018 at 2:52

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.