MInimizing earliness and tardiness costs by ant system approach

The performance of production systems, which are more and more client oriented, strongly depends on the punctuality in the delivery of orders. However, management policies of manufacturing systems have a tendency of reducing batch dimensions which, sometimes, is reduced to a single job. The reason for this tendency is to reduce quantities of stock and to satisfy the customer’s requirements. It is the Just-in-Time approach, in which the production of a job is scheduled after the acquisition of an order, on the basis of the due 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 of jobs has to be carried out and an early or a late delivery implies an incremental cost. The objective is to select a schedule for the jobs in order to minimize the overall penalty cost. The problem taken into account is NP-hard and therefore only heuristic approaches can be used, for increasing problem dimension, which is 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, is innovative. It is based on the Ant Colony Optimization (ACO) paradigm, in which a set of artificial ants explores 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.