MInimizing earliness and tardiness costs by ant system approach

The performance of production systems, which are more and more client oriented, strongly depends on thepunctuality in the delivery of orders. However, management policies of manufacturing systems have atendency of reducing batch dimensions which, sometimes, is reduced to a single job. The reason for thistendency is to reduce quantities of stock and to satisfy the customer’s requirements. It is the Just-in-Timeapproach, in which the production of a job is scheduled after the acquisition of an order, on the basis of thedue date and the actual production capacity of the system.In the present paper, a manufacturing system characterized by a bottleneck station is considered. A set ofjobs has to be carried out and an early or a late delivery implies an incremental cost. The objective is toselect a schedule for the jobs in order to minimize the overall penalty cost. The problem taken into accountis NP-hard and therefore only heuristic approaches can be used, for increasing problem dimension, whichis measured by the number of jobs to be scheduled.We present an approach which, in comparison to those previously proposed in literature on the subject, isinnovative. It is based on the Ant Colony Optimization (ACO) paradigm, in which a set of artificial antsexplores the search space, acquiring and sharing knowledge so as to optimize an objective function,mimicking the foraging behaviour of real ant colonies. The algorithm is tested on benchmark instances.