~spidernet/PermutationFlowShopScheduling

Project from my Advanced Scheduling Systems course in CS master degree
14c4e70a — Alessio Chiapperini 3 months ago
Add empty line before list in readme
fd7c94eb — Alessio Chiapperini 3 months ago
Add README and problem formulation
0baedf19 — Gabriele Venturato 1 year, 2 days ago
Merge branch 'master' of bitbucket.org:spodernet/permutation-flow-shop-scheduling

refs

master
browse log

clone

read-only
https://git.sr.ht/~spidernet/PermutationFlowShopScheduling
read/write
git@git.sr.ht:~spidernet/PermutationFlowShopScheduling

You can also use your local clone with git send-email.

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.

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.