ECF 1.5
flowshop.h
1/* flowshop.h
2 *
3 * (C) 2018 Eva Tuba <etuba@ieee.org> and Carlos M. Fonseca <cmfonsec@dei.uc.pt>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 3 of the License, or (at
8 * your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 */
19
20/* This header file contains all problem dependent definitions */
21
22/* Memory management */
23struct solution *allocSolution(struct problem *p);
24struct move *allocMove(struct problem *p);
25struct pathState *allocPathState(struct problem *p);
26
27void freeProblem(struct problem *p);
28void freeSolution(struct solution *s);
29void freeMove(struct move *v);
30void freePathState(struct pathState *ps);
31
32/* I/O */
33void printProblem(struct problem *p);
34void printSolution(struct solution *s);
35void printMove(struct move *v);
36void printPathState(struct pathState *ps);
37
38/* Solution generation */
39struct solution *randomSolution(struct solution *s);
40
41/* Solution inspection */
42double getObjectiveValue(struct solution *s);
43
44/* Move generation */
45struct move *randomMove(struct move *v, const struct solution *s);
46
47/* Operations on solutions*/
48struct solution *copySolution(struct solution *dest, const struct solution *src);
49struct solution *applyMove(struct solution *s, const struct move *v);
50
51/* Path generation */
52struct pathState *initPathTo(struct pathState *ps, const struct solution *s1, const struct solution *s2);
53struct pathState *initPathAwayFrom(struct pathState *ps, const struct solution *s);
54struct move *nextRandomMove(struct move *v, struct pathState *ps);
55
56/* Path inspection */
57int getPathLength(const struct pathState *ps);
58
59
60/* Problem-specific instantiation */
61struct problem *newProblem(const char *filename);
62
63struct problem {
64 int *data; /* array if size n*m, time needed by job j on machine i */
65 int n, m; /* number of jobs, number of machines */
66};
67
68struct solution {
69 struct problem *prob;
70 int *data;
71 int *times;
72 int n, m; /* number of jobs, number of machines */
73 int objvalue;
74 int eval; /* evaluation needed from this position onwards */
75 int stale; /* deprecated */
76};
77
78struct move {
79 struct problem *prob;
80 int data[2];
81};
82
83struct pathState {
84 struct problem *prob;
85 int *data; /* normalised permutation computed as p2i[p1] */
86 int *pos; /* indices of the LIS followed by the remaining indices
87 in ascending order */
88 int *pred; /* temporary storage for LIS recovery */
89 int n;
90 int in_order;
91};
Definition: flowshop.h:78