Minimization of The Total Tardiness with State Dependent Setups on a Flexible Machine

摘要

Consider the problem of having N jobs which have to be processed on a single flexible machine which has a tool magazine. The tool magazine has a limited capacity of C slots. Each job requires a set of tools and the total number of tools, M, requiredto process all N jobs is greater than C. Also, each job has a processing time on the machine and a due date. A setup time, which depends on the state of the machine, consists of both loading and unloading times of tools. The problem is to find a job sequence and the tools to be loaded on tool magazine of the machine before each job in the sequence such that the total tardiness is minimized. A tabu search algorithm for solving this problem is proposed. The algorithm is tested on some random test problems. Computational results on the proposed algorithm are very encouraging.