Python: Ordering partial elements in List for Genetic Algorithm

Question

I want to solve Job Shop Scheduling problem using Genetic Algorithm and the code will be written in Python.

Currently, I present the individual as a list of [job, operation, machine, operation]. For example, here is example of one chromosome:

jobs = [ [1,3,3,2], [3,3,1,3], [1,1,1,4], [2,2,1,4], [2,3,3,4], [3,1,3,3], [2,1,2,1], [1,2,2,3], [3,2,2,2]  ]

The list must satisfy operation precedence constraint for every job, for example the correct order for job 1 in the list is

[1,1,1,4], [1,2,2,3], [1,3,3,2] 

In other words, I must make ordering for job 1 (index 0, index 2, and index 7) only while the other jobs remain in their position. The correct result will be:

jobs = [ [1,1,1,4], [3,3,1,3], [1,2,2,3], [2,2,1,4], [2,3,3,4], [3,1,3,3], [2,1,2,1], [1,3,3,2], [3,2,2,2]  ]

---

My attempt so far:

Determine/filter all rows that contains job 1:

[row[:][:] for row in jobs if row[0]==1] 

output

[[1, 1, 1, 4], [1, 2, 2, 3], [1, 3, 3, 2]]

Answer 1

The straight-forward way to do this is to make a temporary list of the jobs with the desired job number, and sort that temporary list. Then you need to replace the original items with the sorted ones, and to do that correctly you need to keep track of their positions in the jobs list.

j0 = [[1,3,3,2], [3,3,1,3], [1,1,1,4], [2,2,1,4], [2,3,3,4], 
    [3,1,3,3], [2,1,2,1], [1,2,2,3], [3,2,2,2]]
print(j0)

j1 = [[1,1,1,4], [3,3,1,3], [1,2,2,3], [2,2,1,4], [2,3,3,4], 
    [3,1,3,3], [2,1,2,1], [1,3,3,2], [3,2,2,2]]
print(j1)

def sortjob(alljobs, jobnum):
    #get jobs with this jobnum
    indices = []
    jobs = []
    for i, v in enumerate(alljobs):
        if v[0] == jobnum:
            indices.append(i)
            jobs.append(v)

    jobs.sort()
    #put the sorted jobs back into the correct locations
    for i, v in zip(indices, jobs):
        alljobs[i] = v

sortjob(j0, 1)
print(j0)    

output

[[1, 3, 3, 2], [3, 3, 1, 3], [1, 1, 1, 4], [2, 2, 1, 4], [2, 3, 3, 4], [3, 1, 3, 3], [2, 1, 2, 1], [1, 2, 2, 3], [3, 2, 2, 2]]
[[1, 1, 1, 4], [3, 3, 1, 3], [1, 2, 2, 3], [2, 2, 1, 4], [2, 3, 3, 4], [3, 1, 3, 3], [2, 1, 2, 1], [1, 3, 3, 2], [3, 2, 2, 2]]
[[1, 1, 1, 4], [3, 3, 1, 3], [1, 2, 2, 3], [2, 2, 1, 4], [2, 3, 3, 4], [3, 1, 3, 3], [2, 1, 2, 1], [1, 3, 3, 2], [3, 2, 2, 2]]

Note that sortjob modifies the list that you pass it, just like the list.sort method does, and keeping with the Python convention for such functions sortjob returns None.