A Hybrid Algorithm for a Lot Scheduling Problem

摘要

A hybrid algorithm for the solution of a lot scheduling problem to minimize makespan on non-identical parallel machines under different due date constraints is described. A lot scheduling is defined as the problem of jointly determining the alternative processing machines, the lot size of each product on each machine and the sequence of jobs. Therefore, the lot scheduling problem may be formulated as an optimal combinatorial problem which belongs to the class of NP complete, whcih means that no deterministic algorithm is known yet. So, we propose a hybrid algorithm which uses heuristics in combination with the genetic algorithm. The genetic algorithm takes charge of the global search, on the other hand, heuristics take charge of the local search for the solution of sub-problems. The proposed hybrid method is robust and efficient because it takes advantage of the merits of both methods.