Minimizing maximum tardiness and delivery costs with batch delivery and job release times

Due to high delivery costs, manufacturers are usually required to dispatch their jobs as batches. However, this approach causes several crucial problems in scheduling-related objective functions such as minimizing the maximum tardiness. In this study, we address the scheduling of a set of jobs with specific release times, which need to be processed by a single machine and dispatched to a customer or another machine in a batch delivery condition. Each batch has a particular delivery cost. The aim is to minimize the costs of maximum tardiness plus delivery. First, a mixed integer programming (MIP) model is developed and solved by the CPLEX solver within the GAMS modeling environment. Next, a branch and bound algorithm is developed based on the LP relaxation of the MIP model. Using heuristics, appropriate values for the upper and lower bounds are predicted. The heuristics and pruning rules can obtain the solutions of large problems in logical run times. The problem can be deduced as being NP-hard, so the MIP model is not expected to be solved for extremely large sizes within a reasonable (i.e., polynomially-bounded) CPU time. Hence, by exploiting the features of the problem, two metaheuristic algorithms are developed, i.e., a fast discrete particle swarm optimization and a genetic algorithm. Finally, we present computational results to analyze and verify the solutions obtained.