Use ParadisEO-MOEO to solve the Flowshop problem

This package contains many convenient classes to solve a bi-objective flow-shop scheduling problem within ParadisEO-MOEO. An example using multi-objective evolutionary algorithms is provided.


Download


Problem description

Solving the flow-shop scheduling problem consists of scheduling N jobs on M machines. Machines are critical resources, i.e. two jobs cannot be assigned to one machine simultaneously. A job Ji is composed of M consecutive tasks ti1, ti2, ..., tiM, where tij is the jth task of the job Ji, requiring the machine Mj. A processing time pij is associated to each task tij and a job Ji must be achieved before its due date di. For the permutation flow-shop, the operating sequences of the jobs are identical and unidirectional on every machines. Here, we focus on minimizing both the makespan and the total tardiness, which are two of the most studied objectives of the literature.

Some references about multi-objective scheduling problems:

  • A. Nagar, J. Haddock, and S. Heragu. Multiple and bicriteria scheduling: A literature survey. European Journal of Operational Research, 81:88-104, 1995.
  • V. T'Kindt and J.-C. Billaut. Multicriteria Scheduling: Theory, Models and Algorithms. Springer-Verlag, 2002.
  • J. D. Landa Silva, E. Burke, and S. Petrovic. An introduction to multiobjective metaheuristics for scheduling and timetabling. Metaheuristics for Multiobjective Optimisation, volume 535 of Lecture Notes in Economics and Mathematical Systems, pages 91-129. Springer-Verlag, 2004.


Solver description

This problem is tackled by evolutionary algorithms implemented within ParadisEO-MOEO (see the FlowShopMOEA.cpp file in the archive).

The following components are representation-dependent:

  • FlowShopEval.h: The evaluation function
  • FlowShopEval.cpp
  • FlowShop.h: The genotype
  • FlowShop.cpp
  • FlowShopInit.h: The initializer that constructs the individuals
  • FlowShopInit.cpp
  • FlowShopObjectiveVector.h: The phenotype
  • FlowShopObjectiveVectorTraits.h: Objective parameters
  • FlowShopObjectiveVectorTraits.cpp
  • FlowShopOpCrossoverQuad.h: A quadratic crossover
  • FlowShopOpCrossoverQuad.cpp
  • FlowShopBenchmarkParser.h: Benchmark parser
  • FlowShopBenchmarkParser.cpp
  • FlowShopOpMutationExchange.h: Exchange mutation
  • FlowShopOpMutationExchange.cpp
  • FlowShopOpMutationShift.h: Shift mutation
  • FlowShopOpMutationShift.cpp
  • make_eval_FlowShop.h
  • make_genotype_FlowShop.h
  • make_op_FlowShop.h

The others are generic in ParadisEO-EO and ParadisEO-MOEO.


Instructions

To install the package, follow these steps:

  • Download one of the previous archives and decompress it.
  • Edit the "install.cmake" file and replace "myDirectory" by your absolute path of ParadisEO
    => Example:
SET(PARADISEO_DIR "myDirectory" CACHE PATH "ParadisEO directory" FORCE)
replaced by:
SET(PARADISEO_DIR "/opt/paradiseo-ix86-1.0" CACHE PATH "ParadisEO directory" FORCE)
  • Go in the "build" directory
  • Run (in a terminal/console): cmake .. -G"<generator type>"
    (Several generators exist: see?)
  • Compile using the appropriate tool (run "make" if you choose the "Unix Makefiles" generator)
For an easy use of the application, an install target has been added. It copies the instances directory and the required parameter file FlowShopMOEA.param where you build the main (executable) FlowShopMOEA.cpp.

Then, after a make and another make install, you'll get the instances where the executable is built.

  • Edit the FlowShopMOEA.param to specify the instance you want to use:
--BenchmarkFile=instances/020_10_01.txt # -B : Benchmark file name REQUIRED

... and then run it: FlowShopMOEA @FlowShopMOEA.params


Instances

To evaluate the performance of the algorithms, we propose various benchmark suites available here. These test instances are built from some Taillard instances for the single-objective flow-shop scheduling problem and extended here to the multi-objective case by adding a due date for every job. These benchmarks contain data for problems of N=20, 30, 50, 70, 100, 150, 200, 300 and 500 jobs and of M=5, 10, 15 and 20 machines, with 10 distinct instances per size (N*M). An instance denoted N_M_i represents the ith instance composed of N jobs and M machines.