2001/01/01 by M. E. Kurz, Mary E. Kurz, R. G. Askin +1 · 90 citations
Engineering · Mathematics · #Advanced Manufacturing and Logistics Optimization #Assembly Line Balancing Optimization #Computer science #Heuristic #Heuristics #Integer programming #Job shop scheduling #Mathematical optimization #Mathematics #Routing (electronic design automation) #Scheduling (production processes) #Scheduling and Optimization Algorithms #Sequence (biology) #Set (abstract data type) #Travelling salesman problem
paper · doi:10.1080/00207540110064938
published in International Journal of Production Research 39(16), 3747-3769 (Taylor & Francis)
openalex publication_date 2001/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In many manufacturing environments, multiple processing stations are used in parallel to obtain adequate capacity. Likewise, in many production environments, set-up activities are required for switching between items. This work addresses scheduling in parallel machines with sequence dependent set-up times and possibly non-zero ready times with the goal of minimizing makespan. Non-zero ready times allow for application in a continuous planning environment and will also support the expansion of the current model to a multistage production environment. An integer programming formulation is presented. Several heuristics, including approaches based on MULTI-FIT, genetic algorithms and the travelling salesman problem, are then developed and compared empirically. Seven factors are identified in order to generate problem data, including the number of parallel machines, the average number of jobs per machine, set-up time distribution parameters and processing time distribution parameters. The set-up time matrix can be either symmetric or asymmetric but must satisfy the triangle inequality. A modified insertion heuristic is found to perform best for these types of problems.