|
This paper deals with makespan minimization of a job shop. The job-shop scheduling problem with the makespan criterion is certainly an NP-hard case, hence optimization algorithms are ruled out in practice. It is therefore unrealistic to try obtaining a solution through a commercial solver in polynomial time. This paper proposes a computationally effective heuristic, which is based on the powers of two policy in inventory, for solving the minimum makespan problem of job-shop scheduling. It also proposes bounds for makespan, to validate the results obtained by the proposed heuristic. An increase in resource utilization is noted as an important by-product of the proposed heuristic.
One of the most popular models in scheduling theory is that of the job shop. Job shop is considered to be a good representation of the general domain and has earned a reputation of most difficult to solve among non-deterministic polynomial-time hard (NP-hard) set of scheduling problems. In the job shop case it is more appropriate to describe an operation with triplet (i, j, k) in the order to denote the fact that operation i of job j requires machine k for processing.
In many cases, the combination of goals and resources exponentially increases the search space, and thus the generation of consistently good scheduling is particularly difficult because we have a very large combinatorial search space and precedence constraints between operations (Mesghouni et al., 2004). Due to the NP-hard nature of the scheduling problems, it is usually difficult to find an exact optimal schedule and hence we rely on finding a near to optimal solution. In this regard, a very fruitful approach has been to relax the notion of optimality and settle for near-optimal solutions. A near-optimal solution is one whose objective function value is within some small deviation from the globally optimal value. The near-optimal scheduling algorithms spend time on improving the schedule quality but do not continue until the optimum is found (Hussein, 2005). |
