Tabu search heuristic for two-machine flowshop with batch processing machines

摘要

Batch processing machines are frequently encountered in many industrial environments. A batch processing machine is one which can process several jobs simultaneously as a batch. The processing time of a batch is equal to the largest processing time of any job in the batch. This study deals with the problem of scheduling jobs in a flowshop with two batch processing machines such that the makespan is minimized. A heuristic based on Tabu search (TS) technique is proposed. The proposed heuristic is compared with a heuristic based on mixed integer linear programming (MILP). Because the complexity of the MILP-based heuristic is depended on the number of job batches, the comparison is under up-to-eight batches problem. In order to measure the proposed TS-based heuristic in larger batch problem, the relative error percentage with the lower bound (REP_(LB)) is used. The results show that the proposed heuristic is efficient and effective for the problems with relative large job sizes.