Heuristics and lower bound for minimizing maximum lateness on a batch processing machine with incompatible job families

Production efficiency can be greatly improved by using batch processing machines which can process several jobs in parallel. When job processing characteristics are different, job family should be further considered to group jobs properly in a batch. The problem of scheduling non-identical jobs from incompatible job families on a batch processing machine is investigated in this paper. Job sizes are non-identical and the objective is to minimize the maximum lateness L-max. Batch processing time is determined by the job with the longest processing time and batch due date equals to the earliest job due date in the batch. Only jobs from the same job family can be grouped together in the same batch. A mathematical model of the problem under study is formulated and validated by using CPLEX. A lower bound is proposed based on the lower bound and the upper bound of the batch number. Because of the NP-hardness of the problem, heuristics are designed to solve the problem under study. These heuristics are then improved by optimizing completion time or due date of the critical batch. Experimental studies show that heuristics could be effectively improved by CTD (Completion Time Decreasing) rules. (C) 2019 Elsevier Ltd. All rights reserved.