Bicriterion scheduling with truncated learning effects and convex controllable processing times

• Author: Ji‐Bo Wang,Jian Xu,Dan‐Yang Lv,Ping Ji,Fuqiang Li
• Date: 01 May 2021
• DOI: http://doi.org/10.1111/itor.12888
• Published date: 01 May 2021

Intl. Trans. in Op. Res. 28 (2021) 1573–1593

DOI: 10.1111/itor.12888

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Bicriterion scheduling with truncated learning effects and

convex controllable processing times

Ji-Bo Wanga, Dan-Yang Lva, Jian Xub,∗, Ping Jicand Fuqiang Lid

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

bSchool of Data Science and Artificial Intelligence, Dongbei Universityof Finance and Economics, Dalian 116025,

P.R. China

cDepartment of Industrial and Systems Engineering, The Hong Kong PolytechnicUniversity, Hong Kong, P.R. China

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

P.R. China

E-mail: wangjibo75@163.com [Wang]; 2536959388@qq.com [Lv]; xujian@dufe.edu.cn [Xu]; Jip@polyu.edu.hk [Ji];

243182778@qq.com [Li]

Received 28 July2020; received in revised form 7 October 2020; accepted 8 October 2020

Abstract

This paper investigates single-machine scheduling in which the processing time of a job is a function of its

position in a sequence, a truncation parameter, and its resource allocation. For a convex resource consump-

tion function, we provide a bicriteria analysis where the first is to minimize total weighted flow (completion)

time, and the second is to minimize total resource consumption cost. If the weights are positional-dependent

weights, we prove that three versions of considering the two criteria can be solved in polynomial time, re-

spectively. If the weights are job-dependent weights, the computational complexity of the three versions of

the two criteria remains an open question. To solve the problems with job-dependent weights, we present a

heuristic (an upper bound) and a branch-and-bound algorithm (an exact solution).

Keywords:scheduling; branch-and-bound; combinatorial optimization; heuristics; controllableprocessing time; truncated

learning effect

1. Introduction

In conventional scheduling models, the processing time of a job is generally treated as a constant

value. However, there are many real-world situations in which the processing time of a job may

be subject to change due to learning effects (LE). Learning effects are important for production

problems involving significant level of human activities, such as machine setup, and cleaning, ma-

chine operating and controlling, machine maintenance, machine failure prevention, and all kinds of

∗Corresponding author.

© 2020 The Authors.

International Transactionsin Operational Research © 2020 International Federation of OperationalResearch Societies

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

USA.

1574 J.-B.Wang et al. / Intl. Trans. in Op. Res. 28 (2021) 1573–1593

manual work (Qian and Steiner, 2013). Recent papers on scheduling problems with LE include in

Biskup (2008), Low and Lin (2011), Wu et al. (2011, 2013), Cheng et al. (2013), Azzouz et al.

(2018), Wang et al. (2019), Zhang et al. (2019), and Qian et al. (2020). On the other hand, the

job processing times may be controlled by allocating extra resources (e.g., fuel, gas, or catalyz-

ers), that is, scheduling problems with controllable processing times (CPT) or resource alloca-

tion (RA). Recent papers on scheduling problems with CPT (RA) include in Shabtay and Steiner

(2007), Ji et al. (2015), Oron (2016), Lu and Liu (2018), Fleszar and Hindi (2018), and Wang and

Li (2019).

Recently, there has been increasing attention to the scheduling problems involving both LE and

CPT (RA). Wang et al. (2010) was the first to study scheduling with the effects of learning and

resource allocation, that is, for single machine and the convex resource consumption function,

if job Jjis scheduled in position rin a sequence, its actual processing time is pj(r,uj)=(θjra

uj)η,

where θjis a positive job parameter of job Jj,a≤0 is a learning factor, ujis the amount of

resource that can be allocated to job Jj,andηis a positive constant (see Monma et al., 1990, and

Shabtay and Steiner, 2007). Using the three-field notation introduced by Graham et al. (1979), they

proved that the problems 1|pj(r,uj)=(θjra

uj)η|δ1Cmax +δ2n

j=1cj+δ3TADC+δ4n

j=1gjuj

and 1|pj(r,uj)=(θjra

uj)η|δ1Cmax +δ2n

j=1Wj+δ3TADW +δ4n

j=1gjujcanbesolvedin

O(nlog n) time, where nis the number of jobs, δi≥0(i=1,2,3,4), Cmax is the makespan,

n

j=1cj(n

j=1Wj) is the total completion (waiting) time, TADC =n

j=1n

i=j|cj−ci|

(TADW =n

j=1n

i=j|Wj−Wi|) is the total absolute differences in completion (waiting) times,

cj(Wj=cj−pj) is the completion (waiting) time of job Jj,andgjis the per time unit cost

associated with uj. Lu et al. (2014) considered due date assignment scheduling with the effects

of learning and resource allocation, that is, for the convex resource consumption function,

pj(r,uj)=(θjraj

uj)η,whereaj≤0 is the job-dependent learning factor of job Jj.Theyproved

that the problem 1|CON/SLK,pj(r,uj)=(θjraj

uj)η|n

j=1(δ1Ej+δ2Tj+δ3dj+gjuj)canbesolved

in O(n3) time, where djis the due date of job Jj,Ej=max{0,dj−cj}(Tj=max{0,cj−dj})

is the earliness of job Jj,CON is the common due date assignment (i.e., dj=d,dis a

decision variable), and SLK is the slack due date assignment (i.e., dj=pj+q,qis a deci-

sion variable). Wang and Wang (2015) considered the same model as Lu et al. (2014), they

proved that the problems 1|pj(r,uj)=(θjraj

uj)η,n

j=1uj≤U|δ1Cmax +δ2n

j=1cj+δ3TADC,

1|pj(r,uj)=(θjraj

uj)η,n

j=1uj≤U|δ1Cmax +δ2n

j=1Wj+δ3TADW ,1|CON/SLK/DI F,pj(r,uj)

=(θjraj

uj)η,n

j=1uj≤U|n

j=1(δ1Ej+δ2Tj+δ3dj), 1|pj(r,uj)=(θjraj

uj)η,δ

1Cmax +δ2n

j=1cj+

δ3TADC ≤V|n

j=1uj,1|pj(r,uj)=(θjraj

uj)η,δ

1Cmax +δ2n

j=1Wj+δ3TADW ≤V|n

j=1uj,

1|CON/SLK/DI F,pj(r,uj)=(θjraj

uj)η,n

j=1(δ1Ej+δ2Tj+δ3dj)≤V|n

j=1ujcan be solved

in O(n3) computation, respectively, where Uand Vare given constants, and DIF de-

notes different due date assignment. Wang and Wang (2014) considered common due

window (CONW) assignment scheduling, that is, they proved that 1|CONW,pj(r,uj)=

(θjraj

uj)η|n

j=1(δ1Ej+δ2Tj+δ3d+δ4D)+δ5n

j=1gjujcanbesolvedinO(n3) computa-

tion, where drepresents the starting time of the common due window, Ddenotes the

© 2020 The Authors.

International Transactionsin Operational Research © 2020 International Federation of OperationalResearch Societies