A hybrid heuristic approach to minimize number of tardy jobs in group technology systems

• Author: Paul Bryant,Naeem Bajwa,Sharif Melouk
• Date: 01 September 2019
• Published date: 01 September 2019
• DOI: http://doi.org/10.1111/itor.12406

Intl. Trans. in Op. Res. 26 (2019) 1847–1867

DOI: 10.1111/itor.12406

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A hybrid heuristic approach to minimize number of tardy jobs

in group technology systems

Naeem Bajwaa, Sharif Meloukband Paul Bryantb

aDepartment of Management, University of Arkansasat Little Rock, 2801 South University Avenue, Little Rock, AR

72204, USA

bDepartment of Information Systems, Statistics, and Management Science, University of Alabama, Tuscaloosa,AL

35487-0226, USA

E-mail: anbajwa@ualr.edu[Bajwa]; smelouk@cba.ua.edu [Melouk]; ptbryant@crimson.ua.edu [Bryant]

Received 21 November2016; received in revised form 13 February 2017; accepted 25 February 2017

Abstract

We consider the problem of scheduling jobs on a single machine in a group technology (GT) system with

the objective of minimizing the number of tardy jobs without preemption. In this system, we group jobs

into families such that jobs within a family have similar processing requirements. Hence, no scheduled setup

exists between any two jobs of the same family. However, a sequence-independent setup time occurs between

families. The problem is of practical interest for industries such as plastic manufacturing and metal drawing

operations, which often employ a GT setup. This problem has been discussed in the academic literature and

shown to be NP-hard. However, no solution methods have been proposed in the literature. To solve this

NP-hard problem, we develop a hybrid heuristic based on greedy randomized adaptive search procedure

(GRASP) and particle swarm optimization (PSO) meta-heuristics. We conduct extensive experiments with

respect to problem size and parameter settings. We benchmark the performance of the hybrid heuristic with

a simple GRASP application as well as with optimal solutions. Overall, results show the hybrid heuristic

performs very well, finding optimal solutions for 63% of the problem instances.

Keywords:heuristics; scheduling; group technology; GRASP; tardy jobs

1. Introduction

On-time delivery of customer orders is a key measure, from the customer perspective, of the perfor-

mance of a firm. Frequent late deliveries of customer orders may actually damage the reputation of

a firm. Milgate (2001) observes that as just-in-time delivery is becoming increasingly common, the

reliability of delivery performance has become one of the most important criteria for supplier selec-

tion. Research shows that delivery performance of a firm impacts its marketing performance, which

in turn impacts financial performance (Green et al., 2008). Therefore, the problem of scheduling

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1848 N. Bajwaet al. / Intl. Trans. in Op. Res. 26 (2019) 1847–1867

jobs with the objective of minimizing the number of tardy jobs is of practical interest for a firm

striving to improve its customer service. Furthermore, schedules must be updated periodically as

new customer orders arrive. Clearly, both solution quality and the time to obtain the solution are

of prime importance for a firm.

In this research, we address the problem of scheduling jobs on a single machine in a group

technology (GT) system with the objective of minimizing the total number of tardy jobs. Even

though the problem is NP-hard (Liaee and Emmons, 1997; Liu and Yu, 1999; Cheng et al., 2001),

no heuristic solution exists to solve the problem.Thus, we develop two heuristic solution approaches:

(a) a construction-based search procedure,and (b) a hybrid approachusing elements of construction-

based and population-based meta-heuristics. The former of the two heuristics is an application of

GRASP, whereas, the latter one is a hybrid solution approach that borrows elements from GRASP

and particle swarm optimizationtechniques. Wecreate a random set of problem instances using three

different probability distributions to represent due dates and job processing times. We compare the

heuristic solutions, in terms of solution quality and computational time, with the optimal solutions

across all problem instances. Results show that the hybrid heuristic solutions are optimal for 63%

of problem instances. For the remaining problem instances, the average (maximum) optimality gap

was no more than 0.5% (3.0%). The construction-based heuristic found optimal solutions for 35%

of the test instances with an average(maximum) optimality gap of no more than 1.6% (5.0%) for the

rest of the instances. Both heuristics performed very well in terms of solution times. Most problem

instances were solved in less than 30 seconds, while the maximum time was 48.9 seconds; a fraction

of the time when compared to the 18,970 seconds for complete enumeration.

GT is a type of job shop consisting of subsystems in which each subsystem processes jobs with

similar requirements. Successful implementation of GT may result in improved machine utilization,

better scheduling, and waste minimization. The concept exists in a wide range of applications in

industries such as plastic manufacturing, metal drawingoperations, and machine shops. In a typical

GT environment, “families” contain jobs with similar processing/tooling requirements. Groups

of production resources form cells that individually process certain families of jobs in which the

equipment within cells is not interchangeable. This configuration implies a negligible setup time

requirement when switching from one job to another within the family. The tooling requirements,

however, may differ substantially for each family, thus dictating a major setup between families.

Clearly, benefit exists in processing a complete family before the next one begins. Hence, in a GT

system, all jobs within a family must be processed contiguously. This characteristic differentiates

the GT scheduling problem from other batch-processing problems.

GT systems continue as an area of interest as they offer certain advantages over the traditional

job shop environment. Some of the advantages mentioned in the literature include reduction of

material handling and setup times, reduction of work in process inventories, and shorter lead times

for customers (Flynn,1987; Schaller et al., 2000; Flynn and Jacobs, 1987). Nomden et al. (2008) show

the possibility of achieving significant improvementsin flow times within a GT layout. Successful GT

applications include materials requirement planning, machine loading, and production scheduling,

specifically in the area of small batch discrete parts manufacturing (Wisner and Siferd, 1995).

The remainder of the paper is organized as follows. In Section 2, we present a brief review of

well-researched optimization problems in a GT system. Then, we present a brief review of greedy

randomized adaptation search procedure(GRASP) and its successful application to production and

scheduling problems. Furthermore, we also briefly discuss population-based algorithms. In Section

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies