Research on m‐machine flow shop scheduling with truncated learning effects

• Author: Ji‐Bo Wang,Jian‐Jun Wang,Feng Liu
• Published date: 01 May 2019
• DOI: http://doi.org/10.1111/itor.12323
• Date: 01 May 2019

Intl. Trans. in Op. Res. 26 (2019) 1135–1151

DOI: 10.1111/itor.12323

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Research on m-machine flow shop scheduling with truncated

learning effects

Ji-Bo Wanga, Feng Liub,∗and Jian-Jun Wangc

aSchool of Science, Shenyang Aerospace University,Shenyang 110136, P.R. China

bSchool of Management Science and Engineering, Dongbei University of Finance and Economics, Dalian 116025,

P.R. China

cFaculty of Management and Economics, Dalian University of Technology, Dalian 116024, P.R. China

E-mail: wangjibo75@163.com [Wang]; liufengapollo@163.com [Liu]; wangjianjun_2008@163.com [Wang]

Received 27 January 2016; received in revised form 9 May 2016; accepted 23 May 2016

Abstract

The permutation flowshop problems with truncatedexponential sum of logarithm processing times based and

position-based learning effects are considered in this study. The objective is to minimize makespan and total

weighted completion time, respectively. Several heuristics and a branch-and-bound algorithm are proposed

in this paper. The tight worst-case bounds of some simple heuristics are also given. Numerical experiments

are tested to evaluate the performance of the heuristics and branch-and-bound algorithm.

Keywords:scheduling; branch-and-bound algorithm; heuristic algorithm; learning effect; flow shop

1. Introduction

Deterministic flow shop scheduling models and problems have received considerable attention

for many years (see Gonzalez and Sahni, 1978; Nawaz et al., 1983; Taillard, 1990; Nowicki and

Smutnicki, 1996, 1998; Pinedo, 2002; Framinan and Leisten, 2003; Dhouib et al., 2013; Pan and

Ruiz, 2013; Juanet al., 2014; Xie et al., 2014; Defersha, 2015; Li and Pan, 2015). An extensive survey

of different deterministic flow shop scheduling models and problems can be found in Emmons and

Vairaktarakis (2013). On the other hand, there exist various real-life settings, because firms and

employees perform a task over and over, they have learned how to perform more efficiently. This

phenomenon is known as a “learning effect” in the literature. An extensive survey of different

scheduling models and problems involvingjobs with learning effects can be found in Biskup (2008).

Rudek (2011), Cheng et al. (2013), and Liu and Feng(2014) considered the two-machine makespan

minimization flow shop scheduling with learning effects, Rudek (2011) studied the case of a step

∗Corresponding author.

C

2016 The Authors.

International Transactionsin Operational Research C

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

1136 J.-B.Wang et al. / Intl. Trans. in Op. Res. 26 (2019) 1135–1151

learning curve, Cheng et al. (2013) studied the case of a truncated learning function, and Liu and

Feng (2014) studied the case of convexresource-dependent processing times and learning effect. Xu

et al. (2008), Wu and Lee (2009), Kuoet al. (2012), Li et al. (2013), Lee and Chung (2013), Sun et al.

(2013a, 2013b), Wang and Wang (2012), Wang et al. (2013), Wang and Wang (2014), and Wang

and Zhang (2015) considered the m-machine flow shop scheduling with learning effects. Xu et al.

(2008), Wu and Lee (2009), and Lee and Chung (2013) considered the case of a job-independent

learning effect, Kuo et al. (2012) and Li et al. (2013) considered the case of a time-dependent

learning effect, Sun et al. (2013a) considered the case of general position-dependent learning effects,

Sun et al. (2013b) studied three special models of position-dependent learning curve, Wang and

Wang (2012) studied the case of an exponential learning effect, Wang et al. (2013) studied the case

of a truncated position-based learning effect, Wang and Wang (2014) studied the case of a general

exponential learning effect, Wang and Zhang (2015) studied the case of position-weighted learning

effects.

Recently, Cheng et al. (2015) considered scheduling jobs with a position-weighted learning effect,

that is, if job Jjis scheduled in the rth position, its actual processing time is pjr =pjbr−1

l=1p[l],where

pjis the normal processing time of job Jjand 0 <b≤1 is the learning index for all jobs. However,

the actual processing time of a given job drops to very small precipitously when the normal job

processing times are large in the model (Cheng et al., 2015). Motivated by this observation, Lu et al.

(2015) considered a new scheduling model with exponential sum of logarithmprocessing times based

and position-based learning effects, that is, the actual processing time of a job depends not only on

the total normal processing times of the jobs already processed, and on its scheduled position but

also on a control parameter (pjr =pjmax{(αbr−1

l=1ln p[l]+β)ra,δ},whereα≥0,β ≥0, 0 <b≤1

are parameters obtained empirically, α+β=1, and δis a truncation parameter with 0 1).

They haveproved that several single machine scheduling problemscan be solved in polynomial time.

The importance of flow shop scheduling problems is widely recogniz ed in many manufacturing and

assembling processes, that is, a job often consists of a number of operations that must be processed

in a certain order (Gonzalez and Sahni, 1978; Taillard, 1990; Pinedo, 2002; Framinan and Leisten,

2003; Pan and Ruiz, 2013; Li and Pan, 2015). Hence, in this paper, we consider the same model as

in Lu et al. (2015), but with flow shop scheduling problems. The objective functions are to minimize

the makespan and total weighted completion time, respectively. We present some heuristics and a

branch-and-bound algorithm to solve these two problems.

This paper is organized as follows. General notations and assumptions are presented in the

following section. Heuristics for these two problems are presented in Section 3. Section 4 presents

some lower bounds and incorporates these lower bounds in a branch-and-bound algorithm. Two

well-known heuristics and a branch-and-bound algorithm are adopted in Section 5. Section 6

describes the computational experiments. The last section presents conclusions.

2. Problem setting

There are njobs J={J1,J2,...,Jn}readytobeprocessedonmmachines M1,M2,...,Mmat t ime

0. Each job Jjhas moperations Oij (i=1,2,...,m;j=1,2,...,n),thatis,O1j→O2j→ ··· →

Omj. Operation Oij has to be processed on Mi. Each job must be processed without preemption on

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation ofOperational Research Societies