/*
 * Copyright 2002, 2003, 2004, 2005 - <A href="http://www.koalog.com">Koalog</A>
 */
package com.koalog.jcs.examples;

import java.util.StringTokenizer;
import org.apache.log4j.Category;
import com.koalog.jcs.domain.IntegerDomain;
import com.koalog.jcs.scheduler.Task;
import com.koalog.jcs.scheduler.Disjunctive;
import com.koalog.jcs.solver.BaseVariableHeuristic;
import com.koalog.jcs.solver.IncreasingOrderDomainHeuristic;
import com.koalog.jcs.solver.KeepOrderVariableHeuristic;
import com.koalog.jcs.solver.SplitLowDomainHeuristic;
import com.koalog.jcs.solver.SplitSolver;
import com.koalog.jcs.variable.BaseVariable;
import com.koalog.jcs.variable.Variable;

/**
 * This is a solver for the JSSP.
 *
 * @author Yan Georget
 */    
public class JobShopSolver extends SplitSolver {
    //------------------------------------------------------------------------
    // STATIC PROPERTIES
    //------------------------------------------------------------------------
    private static Category cat = Category.getInstance(JobShopSolver.class);

    //------------------------------------------------------------------------
    // PROPERTIES
    //------------------------------------------------------------------------
    /** The critical machine. */
    int criticalMachine;

    //------------------------------------------------------------------------
    // CONSTRUCTORS
    //------------------------------------------------------------------------
    /**
     * Sole constructor.
     * @param problem a JSSP
     */
    public JobShopSolver(JobShopProblem problem) {
        super(problem);
        criticalMachine = -1;
    }
    
    //------------------------------------------------------------------------
    // METHODS
    //------------------------------------------------------------------------
    /**
     * Returns a critical machine.
     * @return a machine number
     */
    private int getCriticalMachine() {
        JobShopProblem p = (JobShopProblem) problem;
        int machine = -1;
        int slack = Integer.MAX_VALUE;
        int localSlack = Integer.MAX_VALUE;
        for (int i=0; i<p.m; i++) {
            if (BaseVariable.notAllInstantiated(p.order[i])) {
                int l = Task.getLocalSlack(p.task[i]);
                if (l < localSlack) {
                    localSlack = l;
                    machine = i;
                } else if (l == localSlack) {
                    int s = Task.getSlack(p.task[i]);
                    if (s < slack) {
                        slack = s;
                        machine = i;
                    }
                }
            }
        }
// better than:
//         int disorder = Integer.MAX_VALUE;
//         int localDisorder = Integer.MAX_VALUE;
//         for (int i=0; i<p.m; i++) {
//             if (BaseVariable.notAllInstantiated(p.order[i])) {
//                 int l = Disjunctive.getLocalDisorder(p.order[i]);
//                 if (l < localDisorder) {
//                     localDisorder = l;
//                     machine = i;
//                 } else if (l == localDisorder) {
//                     int s = Disjunctive.getDisorder(p.order[i]);
//                     if (s < disorder) {
//                         disorder = s;
//                         machine = i;
//                     }
//                 }
//             }
//         }
        return machine;
    }

    /** @see com.koalog.jcs.solver.BacktrackSolver */
    public boolean choice() {
        JobShopProblem p = (JobShopProblem) problem;
        // we keep the critical machine until its tasks are ordered
        if (criticalMachine == -1 
            || BaseVariable.allInstantiated(p.order[criticalMachine])) {
            criticalMachine = getCriticalMachine();
        }
        if (criticalMachine != -1) {
            setVariableHeuristic(new JobShopVariableHeuristic(p));
            setDomainHeuristic(new SplitLowDomainHeuristic());
            // we split the domain of the selected task
            return super.choice(p.task[criticalMachine]);
        } else {
            setVariableHeuristic(new KeepOrderVariableHeuristic());
            setDomainHeuristic(new IncreasingOrderDomainHeuristic());
            // then we instantiate the dates and the makespan
            return super.choice(p.getVariables());
        }
    }

    //------------------------------------------------------------------------
    // INNER CLASSES
    //------------------------------------------------------------------------
    /**
     * A variable heuristic for the JobShop problem.
     * @author Yan Georget
     */
    static class JobShopVariableHeuristic extends BaseVariableHeuristic {
        /**
         * Sole constructor.
         * @param problem a jobshop problem
         */
        JobShopVariableHeuristic(JobShopProblem problem) {
            super(problem);
        }

        /** @see com.koalog.jcs.solver.BaseVariableHeuristic */
        public int eval(Variable var) {
            JobShopProblem p = (JobShopProblem) problem;
            StringTokenizer tks = new StringTokenizer(var.getName(), "_");
            int machine = Integer.parseInt(tks.nextToken());
            int j = Integer.parseInt(tks.nextToken());
            int disorder = Disjunctive.getDisorder(p.order[machine], j);
            if (disorder == 0) {
                // the task is fully ordered
                return Integer.MIN_VALUE;
            } else {
                return (disorder)*p.ub  
                    + ((IntegerDomain) var.getDomain()).size();
            }
        }
    }
}