Permutation shop flow scheduling

[Mark Cai]

There is python example of flow-shop scheduling in offcie website, however how can I implement a permutation flow-shop scheduling (which is a special case of flow-shop scheduling)?

- The definition of (permutation) flow-shop from wiki.

Flow-shop scheduling is a special case of job-shop scheduling where there is strict order of all operations to be performed on all jobs. 

permutation flow-shop scheduling problem in which the processing order of the jobs on the resources is the same for each subsequent step of processing.

- Code of Cplex to implement permutation flow-shop shceduling:

[1] op_sequences = [sequence_var([operations[i][j] for i in range(NB_JOBS)], name='M{}'.format(j)) for j in range(NB_MACHINES)]

[2] for m in range(1, NB_MACHINES):

[3]   model.add(same_sequence(op_sequences[0], op_sequences[m]))

[Priidik Vilumaa]

Hi,

so you mean that on

process1 - job1, job3, job2

also forces 

process2 - job1, job3, job2

?

Basically, there is a single order of jobs on all machines?

Best,

Priidik

[Mark Cai]

Exactly. In real-world, most assembly line take permutation flow-shop, so I would be benefit a lot people if there is a such example.

By the way, the job-shop take so much time when number of machine >= 5 (number of jobs >= 50).

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/6O92_XGOrak/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/4ff64651-00c3-4dde-a637-bfbe1c2f7b49n%40googlegroups.com.

[Mark Cai]

Following is complete description and code using CPLEX sovler: 

https://github.com/IBMDecisionOptimization/docplex-examples/blob/master/examples/cp/visu/flow_shop_permutation.py

[Laurent Perron]

A flowshop is a jobshop. Only the data changes.

You can use the jobshop examples. 

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/db061e29-051a-4e0a-881d-df97b48be705n%40googlegroups.com.

[Mark Cai]

Thank you for your response. 

The statement seems not 100% correct. You can try it with the dataset from previous links.

Some data happens to be the same result (maybe the probability is not low), but some data would result in different solution.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeYDJR-AQxJsr26KexuBOxfVBRNtecNK_W%3DwdiMBo0Lp1g%40mail.gmail.com.

[Laurent Perron]

I must be missing something:

from the file format (standard jssp and taillard format)

a jobshop is defined by n jobs and m machines, 

each job i has m tasks, with duration dij and executed on machine mij

a flowshop is defined by n jobs and m machines, 

each job i has m tasks, with duration dij and executed on machine j

am I wrong ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CA%2Byr8zHG5B7y1skj35rLgu_2NtG%3DW%2Bq%3DCLkKrQ1OhVZMD9pFTA%40mail.gmail.com.

[Laurent Perron]

So, 

I now see the difference between permutation flowshop and flowshop :-)

To implement a permutation flow shop, you will need 1 circuit constraint that will define the permutation.

Then for each arc, force the precedence on all jobs. This could be adapted from the jobshop_ft06_distance.py example by having only one circuit task.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Mark Cai]

That sounds great. I am going to try that. 

Thank you very much, Laurent.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeYcwwP_7zmqcLha%2BbTbm2EBAuSrpFZ_UddwJz7fe1Bx%2BA%40mail.gmail.com.