Title: Two-machine flow shop scheduling with synchronous material movement

Authors: Kwei-Long Huang; José A. Ventura

Addresses: Institute of Industrial Engineering, 102 Guo-Cing Building, No. 1, Sec. 4, Roosevelt Road, National Taiwan University, Taipei, 106, Taiwan ' The Harold and Inge Marcus Department of Industrial and Manufacturing Engineering, 356 Leonhard Building, The Pennsylvania State University, University Park, PA 16802, USA

Abstract: This study considers a new flow shop scheduling problem with synchronous material movement. Specifically, we consider an automated machining centre that consists of a loading/unloading station, two CNC machining stations, and a material handling device. The material handling device is a rotary table that moves jobs between stations simultaneously. Given a set of jobs that need to be processed in the machining centre, the objective of the problem is to find the sequence that minimises the makespan. This problem can be shown to be NP-hard in the strong sense. A dynamic programming algorithm is proposed to obtain an optimal sequence for small- and medium-size problems. For large-scale problems, two heuristic algorithms are developed to obtain a near-optimal solution in a short time. Computational results for the proposed algorithms are provided.

Keywords: flow shop scheduling; makespan; synchronous material handling; dynamic programming; heuristics; two-machine scheduling; sequencing.

DOI: 10.1504/IJPS.2013.059686

International Journal of Planning and Scheduling, 2013 Vol.1 No.4, pp.301 - 315

Received: 04 Jul 2013
Accepted: 22 Nov 2013
Published online: 30 Jun 2014 *