Title: Minimising the total weighted tardiness and instability for the parallel machine re-scheduling problem with deadlines and ready times

Authors: Sezgin Kaplan; Ghaith Rabadi

Addresses: Department of Industrial Engineering, Turkish Air Force Academy, 34149, Istanbul, Turkey ' Department of Engineering Management and Systems Engineering, Old Dominion University, Norfolk, VA 23529, USA

Abstract: The parallel machine rescheduling problem (PMRP) assumes that the jobs have different ready times and due date-to-deadline windows. PMRP can be defined as updating the existing schedule after being disrupted by job-related events including the arrival of new jobs, departure of an existing job, and changes to job priority. In PMRP, bi-criteria objective function is considered to simultaneously minimise both the total weighted tardiness (schedule quality) and schedule instability. We first formulate the PMRP by revising and extending the mixed integer linear programming (MILP) model of the scheduling problem in Kaplan and Rabadi (2012). Five heuristic algorithms, namely MetaRE, BestINSERT, SEPRE, LSHIFT and SHUFFLE, are introduced to handle the bi-objective PMRP using the developed algorithms by Kaplan and Rabadi (2012, 2013). Experiments have been conducted for small size (12 jobs) and large size (60 size) problems for different types of disruptions.

Keywords: parallel machine rescheduling; total weighted tardiness; TWT; due date-to-deadline window; mixed integer linear programming; MILP; MetaRaPS; instability; parallel machine scheduling; due dates; deadlines; ready times.

DOI: 10.1504/IJPS.2015.072084

International Journal of Planning and Scheduling, 2015 Vol.2 No.2, pp.87 - 109

Received: 18 Aug 2014
Accepted: 24 Nov 2014
Published online: 30 Sep 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article