Heuristic method for the hybrid flow shop problem in batch production

This paper deals with a hybrid flow shop scheduling problem where the objective is to minimize total tardiness. Since the described shop is hybrid, each stage could be composed of one or many identical machines. Preemption and splitting are not allowed. We suppose that machines are available to process incoming jobs without maintenance or unavailable periods. Stages are sequentially placed on the shop, so no transportation time is considered. Jobs are characterized by their release dates and due dates. Each job is composed of a given number of subjobs, which are related to a given class. Untreated subjobs are organized in batch by class in order to simplify production. A batch is composed of a single subjob class, which is associated to a processing time. Since the current problem is considered NP-hard, we propose a two phases heuristic method to find suitable solutions. A mixed integer mathematical model solvable for small instances is also developed. Computational tests are performed to ensure the pertinence of proposed method.