Hybrid flowshop scheduling with job interdependences using evolutionary computing approaches

Abstract

This research deals with production scheduling of manufacturing systems that predominantly consist of hybrid flowshops. Hybrid Flowshop Scheduling (HFS) problems are common in metal working industries. Their solution has significant inferences on company performance in a globally competitive market in terms of production cycle time, delivery dates, warehouse and work-in-process inventory management. HFS problems have attracted considerable research efforts on examining their scientific complexity and practical solution algorithms. In conventional HFS systems, an individual job goes through the flowshop with its own processing route, which has no influence on other jobs. However, in many metal working HFS systems, jobs have interdependent relationships during the process. This thesis focuses on addressing two classes of HFS problems with job interdependence that have been motivated by real-life industrial problems observed from our collaborating companies.

The first class of HFS problems with job interdependence are faced by manufacturers of typically standard metal components where jobs are organized in families according to their machine settings and tools. Family setup times arise when a machine shifts from processing one job family to another. This problem is compounded by the challenges that the formation of job families is different in different stages and only a limited number of jobs can be processed within one setup. This class of problems is defined as HFS with family setup and inconsistent family formation.

The second class of HFS problems with job interdependence is typically faced in a production process consisting of divergent operations where a single input item is converted into multiple output items. Two important challenges have been investigated. One is that one product can be produced following different process routes. The other is that the total inventory capacity is very limited in the company in the sense that the inventory spaces are commonly shared by raw materials, work-in-process items and finished products. This class of problems is defined as HFS with divergent production and common inventory.

The aim is to analyze the general characteristics of HFS with job interdependence and develop effective and practical methodologies that can tackle real-world constraints and reduce the scheduling effort in daily production.

This research has made the following contributions: (1) A V-A-X structural classification has been proposed to represent the divergent (V), convergent (A) and mixed (X) job interdependent relations during the production. (2) A genetic algorithm based approach and a particle swarm optimization based approach have been developed to solve two classes of HFS problems with job interdependence, respectively. The computational results based on actual production data have shown that the proposed solutions are robust, efficient and advantageous for solving the practical problems. (3) A waiting factor approach and delay timetable approach have been developed to extend the solutions space of two classes of HFS problems by inserting intentional idle times into original schedules. The computational results have indicated that better schedules can be obtained in the extended solution spaces.