A Discrete Particle Swarm Optimization to Minimize MaximumTardiness with Batch Delivery and Job Release Times

Due to high delivery costs, manufactures are usually required to dispatch their jobs as batches. This, however, causes some crucial problems in scheduling-related objective functions such as minimizing maximum tardiness. The current paper addresses scheduling a set of jobs with specified release times that are to be processed in a single machine and dispatched to customers or other machines in a batched delivery system. Each batch has a particular delivery cost. The aim is to minimize maximum tardiness plus delivery costs. This is an NP-hard problem. A mathematical model is proposed and solved by a commercial solver. However, such model shows low efficiency in large size problems, so a discrete particle swarm optimization (DPSO) algorithm is developed. Finally, computational results obtained from observations of the DPSO algorithm is provided for some randomly-generated problems.

Keywords:

Scheduling , Batch Delivery , DPSO Algorithm , Maximum Tardiness , Release Time