Permutation FlowShop Scheduling

Project developed in team with Gabriele Venturato.

Problem Formulation

The formulation of the problem and the format of the input instances can be found in the file FlowShop.pdf.

Project Structure

Developed solutions using different techniques:

• MiniZinc model
• Enumeration
• Greedy
• Local Search

Greedy

In greedy our aim was to minimize the tardiness since the instances we have are highly influenced by it. We developed a naive and not very meaningful idea with good results in smaller instances, and a more advanced idea that works better with bigger instances. By the way both of them are not very good. An improvement can be probably performed by dividing the cost components, and ordering elements in more than one way. Further ideas need to be explored.

Local Search

In Local Search we used the library EasyLocal, references can be found in its subfolder. We developed two moves: SwapJobs and MoveJob. Further details can be found in the code. An improvement can be maybe reached modifing the MoveJob move such that it lets move jobs forward and backward (now it only allows to move jobs forward). It's important to take care to the case (i,i+1) because it produces the side effect of moving twice on the same neighbor.