Use ParadisEO-MOEO to solve the Flowshop problem
Flowshop source files are available in "paradiseo-moeo/tutorial/examples/flowshop" directory of Paradiseo.
This package contains many convenient classes to solve a bi-objective flow-shop scheduling problem within ParadisEO-MOEO. Example using multi-objective evolutionary algorithms and dominance-based local searches are provided in MOEO tutorials.
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.
This problem is tackled by evolutionary algorithms implemented within ParadisEO-MOEO.
The following components are representation-dependent:
- FlowShopEval.h: The evaluation function
- FlowShop.h: The genotype
- FlowShopInit.h: The initializer that constructs the individuals
- FlowShopObjectiveVector.h: The phenotype
- FlowShopObjectiveVectorTraits.h: Objective parameters
- FlowShopOpCrossoverQuad.h: A quadratic crossover
- FlowShopBenchmarkParser.h: Benchmark parser
- FlowShopOpMutationExchange.h: Exchange mutation
- FlowShopOpMutationShift.h: Shift mutation
The others are generic in ParadisEO-EO and ParadisEO-MOEO.
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.