123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116 |
- package jobshop.solvers;
-
- import jobshop.Instance;
- import jobshop.Result;
- import jobshop.encodings.ResourceOrder;
- import jobshop.encodings.Schedule;
- import jobshop.solvers.neighborhood.Neighbor;
- import jobshop.solvers.neighborhood.Neighborhood;
- import jobshop.solvers.neighborhood.Nowicki;
-
- import java.io.IOException;
- import java.nio.file.Paths;
- import java.util.ArrayList;
- import java.util.Iterator;
- import java.util.List;
- import java.util.stream.Collectors;
-
- /** An empty shell to implement a descent solver. */
- public class TabooSolver implements Solver {
-
- final Neighborhood<ResourceOrder> neighborhood;
- final Solver baseSolver;
- int maxIter = 3;
- int pts = 10;
- int dureeTaboo = 5;
-
- /** Creates a new taboo solver with a given neighborhood and a solver for the initial solution.
- *
- * @param neighborhood Neighborhood object that should be used to generates neighbor solutions to the current candidate.
- * @param baseSolver A solver to provide the initial solution.
- */
- public TabooSolver(Neighborhood<ResourceOrder> neighborhood, Solver baseSolver) {
- this.neighborhood = neighborhood;
- this.baseSolver = baseSolver;
- }
-
- @Override
- public ArrayList<Result> solve(Instance instance, long deadline) {
- Result result;
- ArrayList<Result> list = new ArrayList<>();
- Schedule schedule = baseSolver.solve(instance, deadline).get(0).schedule.get();
- ResourceOrder resourceOrder = new ResourceOrder(schedule);
- int nbKey = Nowicki.Swap.getNbKey(instance.numMachines, instance.numJobs);
- int[] taboo = new int[nbKey];
- for (int i = 0; i<nbKey; i++) {
- taboo[i] = -1;
- }
- int starMakespan = resourceOrder.toSchedule().get().makespan();
- ResourceOrder starResourceOrder = resourceOrder.copy();
- int bestMakespan;
- Neighbor<ResourceOrder> bestNeighbor;
- int voisinsVisites = 0;
- int k = 0;
- while (deadline - System.currentTimeMillis() > 0 && k <= maxIter) {
- k++;
- bestMakespan = Integer.MAX_VALUE;
- bestNeighbor = null;
- List<Neighbor<ResourceOrder>> generatedNeighbors = neighborhood.generateNeighbors(resourceOrder);
- Iterator<Neighbor<ResourceOrder>> iter = generatedNeighbors.iterator();
- while (iter.hasNext()) {
- voisinsVisites++;
- Neighbor<ResourceOrder> neighbor = iter.next();
- Nowicki.Swap currentSwap = (Nowicki.Swap) neighbor.getChange();
- int currentMakespan = Integer.MAX_VALUE;
- try {
- neighbor.applyOn(resourceOrder);
- Schedule currentSchedule = resourceOrder.toSchedule().get();
- currentMakespan = currentSchedule.makespan();
- neighbor.undoApplyOn(resourceOrder);
- } catch (Exception e) {
- }
- if (taboo[currentSwap.generateKey(instance.numJobs)] < k || currentMakespan < starMakespan) {
- neighbor.applyOn(resourceOrder);
- try {
- Schedule currentSchedule = resourceOrder.toSchedule().get();
- currentMakespan = currentSchedule.makespan();
- if (currentMakespan < bestMakespan) {
- bestMakespan = currentMakespan;
- bestNeighbor = neighbor;
- }
- } catch (Exception e) {
- }
- neighbor.undoApplyOn(resourceOrder);
- }
- }
-
- if (bestNeighbor != null) {
- Nowicki.Swap swap = (Nowicki.Swap) bestNeighbor.getChange();
- taboo[swap.generateKey(instance.numJobs)] = k + dureeTaboo;
- bestNeighbor.applyOn(resourceOrder);
- if (bestMakespan < starMakespan) {
- starMakespan = bestMakespan;
- starResourceOrder = resourceOrder.copy();
- }
- }
-
- if (k % (maxIter/pts) == 0) {
- result = new Result(instance, starResourceOrder.toSchedule(), Result.ExitCause.Timeout);
- result.setVoisinsVisites(voisinsVisites);
- list.add(result);
- }
- }
-
- return list;
- }
-
- @Override
- public void setIterMax(int iterMax) {
- this.maxIter = iterMax;
- }
-
- @Override
- public void setpts(int pts) {
- this.pts = pts;
- }
- }
|