Algorithms for a two‐machine flowshop problem with jobs of two classes

• DOI: http://doi.org/10.1111/itor.12530
• Published date: 01 November 2020
• Date: 01 November 2020

Intl. Trans. in Op. Res. 27 (2020) 3123–3143

DOI: 10.1111/itor.12530

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Algorithms for a two-machine flowshop problem with jobs of

two classes

BongJoo Jeonga, Yeong-Dae Kimband Sang-Oh Shimc,∗

aLG Electronics Production Engineering Research Institute, Pyeongtaek, Korea

bDepartment of Industrial Engineering, Korea Advanced Institute of Science and Technology, Yuseong-gu, Korea

cDepartment of Business Administration, Hanbat National University, Yuseong-gu, Daejeon 305-719, Korea

E-mail: bj-jeong@kaist.ac.kr [Jeong]; ydkim@kaist.ac.kr [Kim]; soshim@hanbat.ac.kr [Shim]

Received 13 May2017; received in revised form 12 November 2017; accepted 15 February 2018

Abstract

We consider a problem of scheduling jobs of two classes of urgencies in a two-machine flowshop with the

objective of minimizing total tardiness of one class for urgent jobs and the maximum completion time of

the other class for non-urgent jobs. Urgent jobs are an important consideration in the real manufacturing

systems, but it has not been studied due to the difficulty of the problem. In this research, a branch-and-

bound (B&B) algorithm is proposed through developing lower bounds, dominance properties, and heuristic

algorithms for obtaining an initial feasible solution. To evaluate the performance of the proposed algorithms,

computational experiments on randomly generatedinstances are performed. Results of the experiments show

that the suggested B&B algorithm can solve problems with up to 20 jobs in a reasonable amount of CPU

time.

Keywords:scheduling; two-machine flowshop; urgent job; multiple objectives; two-agent

1. Introduction

In many manufacturing systems, a common resource is used to satisfy demands of customers of

which the priorities are different and jobs for the demands of the customers may also have different

priorities or urgencies. In semiconductor manufacturing systems, for example, jobs are classified

into two (or more) classes according to the urgencies of jobs: normal jobs and urgent jobs. In such

systems, one of the objectives is to minimize makespan for the nor mal jobs; they may want to

minimize total tardiness of the urgent jobs to satisfy customers’ orders. These urgent jobs are often

called hot jobs, or hot runs,in semiconductor manufacturing companies, and arrivals of urgent jobs

are not rare. For example, prototype products, sample products, or products to replace defective

∗Corresponding author.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 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.

3124 B. J.Jeong et al. / Intl. Trans. in Op. Res. 27 (2020) 3123–3143

products are the examples of the urgent jobs. Lately, the arrivals of urgent jobs are not relatively

rare compared with normal jobs and the products associated with the urgent jobs often account

for 30% to 50% of all products. Therefore, it is important to schedule jobs by considering different

urgencies of jobs.

In this paper, we consider a two-machine flowshop in which thereare two classes of jobs with dif-

ferent urgencies,that is, urgent jobs and normal (non-urgent) jobs. In semiconductor manufacturing

systems, the maximum completion time, that is, makespan, is one of the most important criteria for

normal jobs. Also, the waiting time for urgent jobs is very important. Usually in a real manufactur-

ing system, they want urgent jobs to be processed without any waiting. Assuming that a due date

of the job is defined as the earliest time when the job can be completed with no waiting, the waiting

time can occur in the queue at the machines, which may be equal to the tardiness of the job in this

problem. Therefore, in this study, due date of an urgent job is set to the earliest possible completion

time of the job on machine 2 (completion time of the job on machine 2 when the job is processed

through all machines without waiting). Thus,in this study, the objective of the problemis set to min-

imize a weighted sum of the maximum completion time of normal jobs and total tardiness of urgent

jobs.

Although there are a large numberof research papers on flowshop scheduling problems, relatively

fewer researchers have dealt with flowshop scheduling ones with due date-related measures. Kim

(1993a, 1993b) and Schaller (2005) propose branch-and-bound (B&B) algorithms for flowshop

scheduling problems with the objective of minimizing total tardiness, while Gupta and Hariri

(1997) consider flowshop scheduling problems with the objective of minimizing the number of

tardy jobs. Also, Choi and Kim (2009) and Jeong and Kim (2014) propose B&B algorithms on

two-machine re-entrant flowshops with the objective of minimizing total tardiness. Note that the

flowshop scheduling problem with the objective of minimizing total tardiness is shown to be NP-

hard even for the two-machine case (Koulamas, 1994).

There have been various heuristic algorithms for flowshop scheduling problems with multi-

objective. See Deming (2009) and Yenisey and Yagmahan (2014) for a review of research on multi-

objective flowshop scheduling problems. Because of the difficulty of the multiple-objective flow-

shop scheduling problems, there are fewer studies on optimal solution approaches. Allahverdi and

Aldowaisan (2002) propose a B&B algorithm on no-wait flowshops with a bicriterion objective of

minimizing makespan and total flow time. Yeh and Allahverdi (2004) present a B&B algorithm and

a two-phase heuristic for a three-machine flowshop scheduling problem with a bicriterion objective

of minimizing makespan and total flowtime. Also, Chen et al. (2006) propose a B&B algorithm for

a two-machine flowshop scheduling problem with a bicriterion objective of minimizing a weighted

sum of the maximum tardiness and the total completion time. Dhouib et al. (2013) develop several

versions of simulated annealing algorithms for a flowshop scheduling problem with a bi-objective

of minimizing the number of tardy jobs and makespan.

Although multi-objective problemshave two or more objectivefunctions, most problems consider

only one class of jobs. These problems have two or more common objective functions for all jobs.

However, in problems with multi-class jobs, each class of jobs may have different objective function

according to their class. The problem with multi-class jobs is also called the multi-agent problem in

many researches. Agnetis et al. (2004) study a flowshop scheduling problemwith two classes of jobs

with the objective of minimizing the maximum completion times of the twoclasses of jobs, and show

the problem is NP-hard. Later, Lee et al. (2010) study a two-machine permutation flowshop one with

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies