# Single-Machine Group Scheduling Problems with Variable Job Processing Times

Authors: Ping Ji; Lin Li
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper considers two resource constrained single-machine group scheduling problems. These problems involve variable job processing times (general position-dependent learning effects and deteriorating jobs); that is, the processing time of a job is defined by the function that involves its starting time and position in the group, and groups’ setup time is a positive strictly decreasing continuous function of the amount of consumed resource. Polynomial time algorithms are proposed to optimally solve the makespan minimization problem under the constraint that the total resource consumption does not exceed a given limit and the total resource consumption minimization problem under the constraint that the makespan does not exceed a given limit, respectively.


---

## Body

## 1. Introduction

In classical scheduling theory, the jobs’ processing time is always assumed to be fixed and constant value. Actually, we often encounter the case that job’s processing time may be subject to change due to its position in the production sequence. Many authors have researched this aspect. Mosheiov [1] researched scheduling problems with a learning effect; that is, the production time of a given product is shorter if it is scheduled later rather than earlier in the sequence. Voutsinas and Pappis [2] discussed scheduling jobs with production times deteriorating exponentially over time in remanufacturing environments. The objective was to maximize total value of jobs. Cheng et al. [3] considered some scheduling problems with deteriorating jobs and learning effects. They derived polynomial time optimal solutions for the problems to minimize makespan and total completion time. Sun [4] considered a scheduling model in which deteriorating jobs and learning effect were both considered. The jobs’ actual processing time depended on the processing time of the jobs already processed and their positions. He showed that the problems of minimizing the makespan, total completion time, and the sum of the quadratic job completion times remain polynomially solvable. Toksarı [5] presented a single-machine problem with the unequal release times under learning effect and deteriorating jobs. The objective was to minimize the makespan. He developed a branch-and-bound algorithm to solve it and proposed a heuristic algorithm to obtain a near optimal solution. Wang et al. [6] considered a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. The objective was to determine an optimal schedule so as to minimize the total completion time. They proposed three heuristic algorithms by using the V-shaped property. Wang et al. [7] studied a single-machine scheduling and due window assignment problem, which included deteriorating and learning effect. The objective was to minimize costs for earliness, tardiness, the window location, window size and makespan. They showed that the problem was polynomially solvable. Low and Lin [8] considered the model that the processing time of a job was determined by a function of its starting time and positional sequence in each machine. They discussed different objectives, such as the makespan, total completion time, and weighted completion time. Single-machine scheduling problems could be solved polynomially. They also showed that flow shop scheduling problems were polynomially solvable under some certain conditions. Wang et al. [9] considered flowshop scheduling problems with a general exponential learning effect. The objective was to minimize the makespan, the total (weighted) completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times, respectively. They proposed several simple heuristic algorithms to solve these problems and gave the tight worst-case bound of these heuristic algorithms.In manufacturing industry, firms can increase production efficiency by using group technology (GT). GT is an approach in manufacturing that seeks to improve efficiency in high-volume production by exploiting the similarities of different products and activities in their production. Many researchers have paid great attention to this area and done a lot of work. Kuo and Yang [10] introduced a time-dependent learning effect into single-machine group scheduling problems. The time-dependent learning effect of a job is assumed to be a function of total processing times of jobs scheduled in front of it. They showed that the single-machine group scheduling problem with a time-dependent learning effect remains polynomially solvable for two objectives: minimizing the makespan and the total completion time. Wu et al. [11] considered two single-machine scheduling problems in the context of group technology where job processing times and setup times are simple linear functions of their starting times. The objectives were minimization of makespan and total completion time. Yan et al. [12] studied the single-machine scheduling problem with the effects of deterioration and learning, where the jobs were under group consumption and the setup time of each group was dependent on the resource it consumed. Zhang and Yan [13] introduced a deteriorated and learning effect into a single-machine problem where the learning effect not only depends on job position, but also depends on the group position; the deteriorated effect depends on its starting time of the job. They showed that the makespan, the total completion time, and maximum lateness problems remained polynomially optimally solvable under the proposed model. S. J. Yang and D. L. Yang [14] investigated single-machine group scheduling problems. The group setup time was assumed to follow a simple linear time-dependent deteriorating model. They examined two models of learning for the job processing time, provided polynomial time solutions for the makespan minimization problems, and showed that the total completion time minimization problems remained polynomially solvable under agreeable conditions. Zhu et al. [15] studied group scheduling problems with learning effects and resource allocation concurrently. They determined an optimal group sequence, internal job sequence, and the amount of resource allocated for two objectives, respectively. One was to minimize the weighted sum of makespan and total resource cost. The other was to minimize the weighted sum of total completion time and total resource cost. Lee and Lu [16] considered a single-machine scheduling problem in the context of group technology where the job processing times and the group setup times are simple linear functions of their starting times. The objective is to minimize the total weighted number of late jobs. They provided a branch-and-bound algorithm to solve the problem. Huang et al. [17] and Huang and Wang [18] considered two group scheduling problems with time and position-dependent processing times. Ji et al. [19] discussed group scheduling and job-dependent due window assignment problem and provided a polynomial algorithm to solve it. More recent papers have considered scheduling jobs with deteriorating jobs and/or learning effects including Wu et al. [11], Wu and Lee [20], Wang et al. [21], Wang [22], Yin et al. [23], Wang et al. [24], Lee and Wu [25], Li et al. [26], Zhu et al. [27], Huang et al. [28], Janiak and Rudek [29], Ji and Cheng [30], Yang [31], Yin and Xu [32], Bai et al. [33], Yin et al. [34], Yin et al. [35], J. B. Wang and J. J. Wang [36], Wu et al. [37], and Xu et al. [38].Yan et al. [12] and Huang and Wang [18] considered the single-machine scheduling problems with the effects of learning and/or deterioration under the group technology consumption. They proved that the single-machine makespan minimization problem and total resource minimization problem under the group technology consumption remain polynomially solvable. This paper extends the results of Yan et al. [12] and Huang and Wang [18], by considering more general position-dependent learning effects and deteriorating jobs model that includes the one given in Yan et al. [12] and Huang and Wang [18] as a special case. The remaining part of this paper is organized as follows. In Section 2 we describe and formulate the problem. In Sections 3 and 4 we consider two resource-dependent scheduling problems and present polynomial algorithms to solve them. The last section includes conclusions.


## 2. Problem Formulation

There aren jobs to be processed on a single-machine, and these n jobs grouped into m groups. A setup time is required if the machine switches from one group to another and all setup times of groups for processing are at time 0. The machine can handle one job at a time and job preemption is not allowed. Let J
i
j denote the jth job in group G
i, i
=
1,2
,
…
,
m; j
=
1,2
,
…
,
n
i, where n
i denote the number of jobs belonging to group G
i  (i.e., n
1
+
n
2
+
⋯
+
n
m
=
n). Let s
i be the (actual) setup time of group G
i, and let p
i
j
r
(
t
) be the (actual) processing time of job J
i
j if it is started at time t and scheduled in position r. In this paper, we consider the following model:(1)
p
i
j
r
t
=
p
i
j
A
±
B
t
f
i
r
,where p
i
j denotes the normal processing time for job J
i
j, A
≥
0, B
≥
0. f
i
(
r
)
≥
f
i
(
r
+
1
) is the general case of positional learning for group G
i, specially f
i
(
r
)
=
r
a
i (a
i
≤
0 is the polynomial learning index for group G
i) and f
i
(
r
)
=
b
i
r
-
1 (0
<
b
i
≤
1 is the exponential learning index for group G
i). In addition, the setup time s
i is(2)
s
i
=
g
u
i
,
u
_
≤
u
i
≤
u
¯
,
i
=
1,2
,
…
,
m
,where u
i is the amount of a nonrenewable resource allocated to group G
i, with 0
≤
u
i
≤
u
¯, u
¯ is a technological constraint, and g
:
R
+
→
R
+ (R
+ is the set of nonnegative real numbers) is a strictly decreasing continuous function with g
(
u
¯
)
≥
0. Let u
=
(
u
1
,
u
2
,
…
,
u
n
) be the resource allocation vector satisfying the resource constraint ∑
j
=
1
n
‍
u
j
≤
U, where U is the total amount of the resource available.For a given scheduleπ, let C
i
j
=
C
i
j
(
π
) be the completion time of job J
i
j under π, and let C
m
a
x
=
m
a
x
{
C
i
j
∣
i
=
1,2
,
…
,
m
;
j
=
1,2
,
…
,
n
i
} be the makespan (the maximal completion time) of a given schedule. We consider two problems: (1) minimizing the makespan with a resource consumption constraint and (2) the total resource consumption with a makespan constraint. Using the three-field notation (Graham [39]) for scheduling problems, these two problems can be denoted by 1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
±
B
t
)
f
i
(
r
), G
T, ∑
j
=
1
n
‍
u
j
≤
U
∣
C
m
a
x and 1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
±
B
t
)
f
i
(
r
), G
T, C
m
a
x
≤
C
∣
∑
‍
u
j.


## 3. The Problem1
∣
s
i
=
g
(
u
i
)
,
p
i
j
r
(
t
)
=
p
i
j
(
A
±
B
t
)
f
i
(
r
)
,
G
T
,
∑
j
=
1
n
‍
u
j
≤
U
∣
C
max

Lemma 1.
For a given scheduleπ
=
[
J
[
1
]
,
J
[
2
]
,
…
,
J
[
n
]
], if the first job starts at time t
0
≥
0, then the completion time C
j is equal to(3)
C
j
=
t
0
±
A
B
∏
i
=
1
j
‍
1
±
B
p
i
f
i
∓
A
B
,where [
j
]
=
i means job J
i is the jth one to be processed.Proof (by mathematical induction method).
For jobJ
[
1
], we have(4)
C
1
=
t
0
+
p
1
A
±
B
t
0
f
1
=
t
0
±
A
B
1
±
B
p
1
f
1
∓
A
B
.
Suppose Lemma1 holds for job J
[
j
]; that is,(5)
C
j
=
t
0
±
A
B
∏
i
=
1
j
‍
1
±
B
p
i
f
i
∓
A
B
.Then, for job J
[
j
+
1
], we have(6)
C
j
+
1
=
C
j
+
p
j
+
1
A
±
B
C
j
f
j
+
1
=
t
0
±
A
B
∏
i
=
1
j
+
1
‍
1
±
B
p
i
f
i
∓
A
B
.Hence, Lemma 1 holds.Theorem 2.
For the1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
±
B
t
)
f
i
(
r
), G
T
∣
C
m
a
x problem, and a given schedule π
=
[
G
[
1
]
,
G
[
2
]
,
…
,
G
[
m
]
]
=
[
J
1
[
1
]
,
J
1
[
2
]
,
…
,
J
[
1
]
[
n
1
]
,
J
2
[
1
]
,
J
2
[
2
]
,
…
,
J
[
2
]
[
n
2
]
,
…
,
J
[
m
]
[
1
], J
[
m
]
[
2
]
,
…
,
J
[
m
]
[
n
m
]
], the makespan is equal to(7)
C
m
a
x
=
C
m
n
m
=
∑
i
=
1
m
‍
s
i
∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
±
A
B
∏
i
=
1
m
‍
∏
j
=
1
n
i
‍
1
±
B
p
i
j
f
i
j
∓
A
B
.Proof (by mathematical induction method).
Stemming from Lemma1, for group G
[
1
], we have(8)
C
1
n
1
=
s
1
±
A
B
∏
j
=
1
n
1
‍
1
±
B
p
1
j
f
1
j
∓
A
B
.
Suppose Theorem2 holds for group G
[
k
]; that is,(9)
C
k
n
k
=
∑
i
=
1
k
‍
s
i
∏
l
=
i
k
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
±
A
B
∏
i
=
1
k
‍
∏
j
=
1
n
i
‍
1
±
B
p
i
j
f
i
j
∓
A
B
.Then, for group G
[
k
+
1
], we have (10)
C
k
+
1
n
k
+
1
=
C
k
n
k
+
s
k
+
1
±
A
B
×
∏
j
=
1
n
k
+
1
‍
1
±
B
p
k
+
1
j
f
k
+
1
j
∓
A
B
=
∑
i
=
1
k
‍
s
i
∏
l
=
i
k
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
±
∑
i
=
1
k
‍
s
i
∏
l
=
i
k
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
A
B
∏
i
=
1
k
‍
∏
j
=
1
n
i
‍
1
±
B
p
i
j
f
i
j
∓
A
B
+
s
k
+
1
±
A
B
×
∏
j
=
1
n
k
+
1
‍
1
±
B
p
k
+
1
j
f
k
+
1
j
∓
A
B
=
∑
i
=
1
k
+
1
‍
s
i
∏
l
=
i
k
+
1
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
±
A
B
∏
i
=
1
k
+
1
‍
∏
j
=
1
n
i
‍
1
±
B
p
i
j
f
i
j
∓
A
B
.Hence, Theorem 2 holds.Theorem 3.
For the1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
±
B
t
)
f
i
(
r
), G
T
∣
C
m
a
x problem, the optimal job sequence in each group can be obtained by the smallest processing time (SPT) first rule (i.e., arranging jobs in nondecreasing order of p
i
j).Proof.
It is similar to the proof of Bai et al. [33].Theorem 4.
For the1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
+
B
t
)
f
i
(
r
), G
T
∣
C
m
a
x problem, the groups scheduled earlier should be given the priority to resource allocation for any schedule of the groups.Proof.
We assumeπ
=
[
G
[
1
]
,
G
[
2
]
,
…
,
G
[
m
]
] is any schedule of all the groups. Stemming from (7), first allocate the resource to the group, whose setup time s
[
i
] is bigger than ∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
(
1
+
B
p
[
l
]
[
j
]
f
[
l
]
(
j
)
); the makespan can be minimized by the same amount of resource. Obviously(11)
∏
l
=
1
m
‍
∏
j
=
1
n
l
‍
1
+
B
p
l
j
f
l
j
≥
∏
l
=
2
m
‍
∏
j
=
1
n
l
‍
1
+
B
p
l
j
f
l
j
≥
⋯
≥
∏
l
=
m
m
‍
∏
j
=
1
n
l
‍
1
+
B
p
l
j
f
l
j
≥
1
.Hence, for the objective C
m
a
x, the groups scheduled earlier should be given the priority to resource allocation.Theorem 5.
For the1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
-
B
t
)
f
i
(
r
), G
T
∣
C
m
a
x problem, the groups scheduled later should be given the priority to resource allocation for any schedule of the groups.Proof.
We assumeπ
=
[
G
[
1
]
,
G
[
2
]
,
…
,
G
[
m
]
] is any schedule of all the groups. Stemming from (7), first allocate the resource to the group, whose setup time s
[
i
] is bigger than ∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
(
1
-
B
p
[
l
]
[
j
]
f
[
l
]
(
j
)
); the makespan can be minimized by the same amount of resource. Obviously(12)
∏
l
=
1
m
‍
∏
j
=
1
n
l
‍
1
-
B
p
l
j
f
l
j
≤
∏
l
=
2
m
‍
∏
j
=
1
n
l
‍
1
-
B
p
l
j
f
l
j
≤
⋯
≤
∏
l
=
m
m
‍
∏
j
=
1
n
l
‍
1
-
B
p
l
j
f
l
j
≤
1
.Hence, for the objective C
m
a
x, the groups scheduled later should be given the priority to resource allocation.Theorem 6.
For the1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
±
B
t
)
f
i
(
r
), G
T
∣
C
m
a
x problem, if resource amount of the groups in each position is fixed and in each group the jobs are scheduled by the SPT rule, then the optimal schedule can be obtained by scheduling the groups in nonincreasing order of ρ
G
i
=
∏
j
=
1
n
i
‍
(
1
±
B
p
i
j
f
i
(
j
)
).Proof.
Without loss of generality, we assume that the resource amount of the group scheduled at theith position is denoted by u
[
i
]  (
i
=
1,2
,
…
,
m
). Let π
=
[
G
[
1
]
,
G
[
2
]
,
…
,
G
[
v
-
1
]
,
G
v
,
G
v
+
1
,
G
[
v
+
2
]
,
…
,
G
[
m
]
] be a schedule and let π
′
=
[
G
1
,
G
2
,
…
,
G
v
-
1
,
G
v
+
1
,
G
v
,
G
v
+
2
,
…
,
G
m
] be a new schedule by changing the sequence of G
v and G
v
+
1. Obviously, for schedule π
′, G
v
(
G
v
+
1
) is scheduled in the (
v
+
1
)th (vth) position; then the resource allocation amount of G
v
(
G
v
+
1
) is u
[
v
+
1
]
(
u
[
v
]
). Then, under the schedules π and π
′, we have(13)
C
m
a
x
π
=
f
u
1
∏
l
=
1
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
+
f
u
2
∏
l
=
2
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
+
⋯
+
f
u
v
-
1
∏
l
=
v
-
1
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
+
f
u
v
∏
l
=
v
+
2
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
×
∏
j
=
1
n
v
‍
1
±
B
p
v
j
f
v
j
×
∏
j
=
1
n
v
+
1
‍
1
±
B
p
v
+
1
j
f
v
+
1
j
+
f
u
v
+
1
∏
l
=
v
+
2
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
×
∏
j
=
1
n
v
+
1
‍
1
±
B
p
v
+
1
j
f
v
+
1
j
+
f
u
v
+
2
∏
l
=
v
+
2
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
+
⋯
+
f
u
m
∏
l
=
m
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
±
A
B
∏
i
=
1
m
‍
∏
j
=
1
n
i
‍
1
±
B
p
i
j
f
i
j
∓
A
B
,
C
m
a
x
π
′
=
f
u
1
∏
l
=
1
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
+
f
u
2
∏
l
=
2
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
+
⋯
+
f
u
v
-
1
∏
l
=
v
-
1
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
+
f
u
v
∏
l
=
v
+
2
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
×
∏
j
=
1
n
v
‍
1
±
B
p
v
j
f
v
j
×
∏
j
=
1
n
v
+
1
‍
1
±
B
p
v
+
1
j
f
v
+
1
j
+
f
u
v
+
1
∏
l
=
v
+
2
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
×
∏
j
=
1
n
v
‍
1
±
B
p
v
j
f
v
j
+
f
u
v
+
2
∏
l
=
v
+
2
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
+
⋯
+
f
u
m
∏
l
=
m
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
±
A
B
∏
i
=
1
m
‍
∏
j
=
1
n
i
‍
1
±
B
p
i
j
f
i
j
∓
A
B
.Then(14)
C
m
a
x
π
-
C
m
a
x
π
′
=
f
u
v
+
1
∏
l
=
v
+
2
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
×
∏
j
=
1
n
v
+
1
‍
1
±
B
p
v
+
1
j
f
v
+
1
j
-
∏
j
=
1
n
v
‍
1
±
B
p
v
j
f
v
j
≤
0if and only if ∏
j
=
1
n
v
+
1
‍
(
1
±
B
p
v
+
1
[
j
]
f
v
+
1
(
j
)
)
≤
∏
j
=
1
n
v
‍
(
1
±
B
p
v
[
j
]
f
v
(
j
)
).Based on Theorems3, 4, and 6, an algorithm can be proposed to solve 1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
+
B
t
)
f
i
(
r
), G
T, ∑
j
=
1
n
‍
u
j
≤
U
∣
C
m
a
x.Algorithm 7.
We have the following.
Step 1. Jobs in each group are scheduled by the SPT rule; that is,(15)
p
i
1
≤
p
i
2
≤
⋯
≤
p
i
n
i
,
i
=
1,2
,
…
,
m
.
Step 2. Groups are scheduled in nonincreasing order of ρ
G
[
i
]
=
∏
j
=
1
n
i
‍
(
1
+
B
p
[
i
]
[
j
]
f
[
i
]
(
j
)
); that is,(16)
ρ
G
1
≥
ρ
G
2
≥
⋯
≥
ρ
G
m
.
Step 3. For the obtained schedule π
=
[
G
[
1
]
,
G
[
2
]
,
…
,
G
[
m
]
], set u
[
i
]
∗
=
0  (
i
=
1,2
,
…
,
m
) and l
=
1.
Step 4. Set u
[
l
]
∗
=
m
i
n
{
u
¯
,
U
}, U
=
U
-
u
[
l
]
∗, and l
=
l
+
1.
Step 5. If U
=
0 or l
=
m
+
1, stop; else go to Step 4.Based on Theorems3, 5, and 6, an algorithm can be proposed to solve 1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
-
B
t
)
f
i
(
r
), G
T, ∑
j
=
1
n
‍
u
j
≤
U
∣
C
m
a
x.Algorithm 8.
We have the following.
Step 1. Jobs in each group are scheduled by the SPT rule; that is,(17)
p
i
1
≤
p
i
2
≤
⋯
≤
p
i
n
i
,
i
=
1,2
,
…
,
m
.
Step 2. Groups are scheduled in nonincreasing order of ρ
G
[
i
]
=
∏
j
=
1
n
i
‍
(
1
+
B
p
[
i
]
[
j
]
f
[
i
]
(
j
)
); that is,(18)
ρ
G
1
≥
ρ
G
2
≥
⋯
≥
ρ
G
m
.
Step 3. For the obtained schedule π
=
[
G
[
1
]
,
G
[
2
]
,
…
,
G
[
m
]
], set u
[
i
]
∗
=
0  (
i
=
1,2
,
…
,
m
) and l
=
m.
Step 4. Set u
[
l
]
∗
=
m
i
n
{
u
¯
,
U
}, U
=
U
-
u
l
∗, and l
=
l
-
1.
Step 5. If U
=
0 or l
=
0, stop; else go to Step 4.Obviously the total time for Algorithm7 (Algorithm 8) is O
(
n
l
o
g
n
).The following example is used to illustrate Algorithm7.Example 9.
Considern
=
6, m
=
3, f
i
(
r
)
=
r
a
i, and g
(
u
i
)
=
6
-
u
i. The normal processing times p
i
j, a
i for each group are given in Table 1, A
=
1, B
=
0.1, u
¯
=
5, and U
=
10.Table 1
The date of Example9.
Group
G
1
G
2
G
3
J
i
j
J
11
J
12
J
21
J
22
J
31
J
32
p
i
j
12
8
20
10
15
18
a
i
−0.2
−0.3
−0.1Solution. According to Algorithm 7, we solve Example 9 as follows.Step 1. In group G
1, the optimal job sequence is J
12
→
J
11. In group G
2, the optimal job sequence is J
22
→
J
21. In group G
3, the optimal job sequence is J
31
→
J
32.Step 2. Consider ρ
(
G
1
)
=
3.6804
<
ρ
(
G
2
)
=
5.2490
<
ρ
(
G
3
)
=
6.6987.Step 3. The obtained schedule is π
=
[
G
3
,
G
2
,
G
1
].Steps 4 and 5. The optimal resources u
3
∗
=
m
i
n
{
u
¯
,
U
}
=
5, u
2
∗
=
5, u
1
∗
=
0.Therefore, the optimal schedule is[
J
31
→
J
32
]
→
[
J
22
→
J
21
]
→
[
J
12
→
J
11
], and the optimal completion times are calculated as follows:(19)
s
3
=
6
-
5
=
1
,
C
31
=
1
+
15
∗
1
+
0.1
∗
1
∗
1
-
0.1
=
17.5
,
C
32
=
17.5
+
18
∗
1
+
0.1
∗
17.5
∗
2
-
0.1
=
63.6851
,
s
2
=
6
-
5
=
1
,
C
22
=
63.6851
+
1
+
10
∗
1
+
0.1
∗
63.6851
+
1
∗
1
-
0.3
=
139.3702
,
C
21
=
139.3702
+
20
∗
1
+
0.1
∗
139.3702
∗
2
-
0.3
=
382.0228
,
s
1
=
6
-
0
=
6
,
C
12
=
382.0228
+
6
+
8
∗
1
+
0.1
∗
6
+
382.0228
∗
1
-
0.2
=
706.4410
,
C
11
=
706.4410
+
12
∗
1
+
0.1
∗
706.4410
∗
2
-
0.2
=
1454.879
.HenceC
m
a
x
=
C
12
=
1454.879.


## 4. The Problem1
∣
s
i
=
g
(
u
i
)
,
p
i
j
r
(
t
)
=
p
i
j
(
A
±
B
t
)
f
i
(
r
)
,
G
T
,
C
max
≤
C
∣
∑
‍
u
j

Similar to Section3, we only need to consider the schedule in which the jobs in each group are scheduled by the SPT rule, and the groups scheduled in nonincreasing order of ρ
G
[
i
]
=
∏
j
=
1
n
i
‍
(
1
±
B
p
[
i
]
[
j
]
f
[
i
]
(
j
)
) and the groups scheduled earlier (later) should be given the priority to resource allocation for the problem 1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
+
B
t
)
f
i
(
r
), G
T, C
m
a
x
≤
C
∣
∑
‍
u
j
(
1
∣
s
i
=
g
(
u
i
)
,
p
i
j
r
(
t
)
=
p
i
j
(
A
-
B
t
)
f
i
(
r
)
,
G
T
,
C
m
a
x
≤
C
∣
∑
‍
u
j).For a given scheduleπ
=
[
G
[
1
]
,
G
[
2
]
,
…
,
G
[
m
]
] = [
J
1
[
1
]
,
J
1
[
2
]
,
…
,
J
[
1
]
[
n
1
]
,
J
2
[
1
]
,
J
2
[
2
]
,
…
,
J
[
2
]
[
n
2
]
,
…
,
J
[
m
]
[
1
], J
[
m
]
[
2
]
,
…
,
J
[
m
]
[
n
m
]
], stemming from (7), the minimum makespan of this schedule is(20)
C
m
a
x
=
∑
i
=
1
m
‍
f
u
¯
∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
±
A
B
∏
i
=
1
m
‍
∏
j
=
1
n
i
‍
1
±
B
p
i
j
f
i
j
∓
A
B
.So, the schedule π is feasible only if(21)
C
m
a
x
=
∑
i
=
1
m
‍
f
u
¯
∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
1
±
B
p
l
j
f
l
j
±
A
B
∏
i
=
1
m
‍
∏
j
=
1
n
i
‍
1
±
B
p
i
j
f
i
j
∓
A
B
≤
C
.Since the problem is to minimize the total resource consumption with a makespan constraint, then resource consumption of groups should be given as few as possible and the completion time of the last group isC; that is, C
m
a
x
=
C.Without loss of generality, letπ
=
[
G
[
1
]
,
G
[
2
]
,
…
,
G
[
m
]
]
=
[
J
1
[
1
]
,
J
1
[
2
]
,
…
,
J
[
1
]
[
n
1
]
,
J
2
[
1
]
,
J
2
[
2
]
,
…
,
J
[
2
]
[
n
2
]
,
…
,
J
[
m
]
[
1
], J
[
m
]
[
2
]
,
…
,
J
[
m
]
[
n
m
]
] be the schedule in which the jobs in each group are scheduled by the SPT rule and the groups scheduled in nonincreasing order of ρ
G
[
i
]
=
∏
j
=
1
n
i
‍
(
1
±
B
p
[
l
]
[
j
]
f
[
l
]
(
j
)
).For the problem1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
+
B
t
)
f
i
(
r
), G
T, C
m
a
x
≤
C
∣
∑
‍
u
j, if we only allocate the resource to the setup time of group G
[
1
] and for the groups scheduled after it the resource allocation amount is 0, then according to (7), we have(22)
C
=
s
1
∏
l
=
1
m
‍
∏
j
=
1
n
l
‍
1
+
B
p
l
j
f
l
j
+
s
∑
i
=
2
m
‍
∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
1
+
B
p
l
j
f
l
j
+
A
B
∏
i
=
1
m
‍
∏
j
=
1
n
i
‍
1
+
B
p
i
j
f
i
j
-
A
B
=
s
1
∏
l
=
1
m
‍
∏
j
=
1
n
l
‍
1
+
B
p
l
j
f
l
j
+
s
∑
i
=
2
m
‍
∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
1
+
B
p
l
j
f
l
j
+
K
,where s
=
g
(
0
) and K
=
(
A
/
B
)
∏
i
=
1
m
‍
∏
j
=
1
n
i
‍
1
+
B
p
[
i
]
[
j
]
f
[
i
]
(
j
)
-
A
/
B. Hence(23)
s
1
=
C
-
K
-
s
∑
i
=
2
m
‍
∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
1
+
B
p
l
j
f
l
j
∏
l
=
1
m
‍
∏
j
=
1
n
l
‍
1
+
B
p
l
j
f
l
j
.Ifs
[
1
]
≥
g
(
0
), then the constraint C
m
a
x
≤
C can be satisfied even if the resource allocation amount u
[
1
] of G
[
1
] is 0. And we do not have to allocate the resource to the groups; stop.Ifg
(
u
¯
)
≤
s
[
1
]
<
g
(
0
), then the optimal resource allocation is u
[
1
]
∗
=
g
-
1
(
s
[
1
]
), u
[
j
]
∗
=
0, j
=
2
,
…
,
n.Ifs
[
1
]
<
g
(
u
¯
), then the optimal resource allocation of group G
[
1
] should be u
¯; that is, u
[
1
]
∗
=
u
¯. And the optimal resource consumption u
[
j
]
∗, j
=
2
,
…
,
n, can be calculated by the same method.Based on the above analysis, we propose an algorithm to solve the problem1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
+
B
t
)
f
i
(
r
), G
T, C
m
a
x
≤
C
∣
∑
‍
u
j.Algorithm 10.
We have the following.
Step 1. Jobs in each group are scheduled in nondecreasing order of p
i
j; that is,(24)
p
i
1
≤
p
i
2
≤
⋯
≤
p
i
n
i
,
i
=
1,2
,
…
,
m
.
Step 2. Groups are scheduled in nonincreasing order of ρ
G
[
i
]
=
∏
j
=
1
n
i
‍
(
1
+
B
p
[
i
]
[
j
]
f
[
i
]
(
j
)
); that is,(25)
ρ
G
1
≥
ρ
G
2
≥
⋯
≥
ρ
G
m
.
Step 3. For the obtained schedule π
=
[
G
[
1
]
,
G
[
2
]
,
…
,
G
[
m
]
], set u
[
i
]
∗
=
0  (
i
=
1,2
,
…
,
m
), U
=
0, s
=
g
(
0
), s
′
=
g
(
u
¯
), l
=
1, and C
′
=
C
-
K.
Step 4. Calculate(26)
s
l
=
C
′
-
s
∑
i
=
l
+
1
m
‍
∏
k
=
i
m
‍
∏
j
=
1
n
k
‍
1
+
B
p
k
j
f
k
j
∏
i
=
l
m
‍
∏
j
=
1
n
i
‍
1
+
B
p
i
j
f
i
j
.If l
=
m
+
1, stop; else go to Step 5.
Step 5. If s
[
l
]
≥
g
(
0
), stop.
Ifg
(
u
¯
)
≤
s
[
l
]
<
g
(
0
), set u
l
∗
=
g
-
1
(
s
[
l
]
) and U
=
U
+
u
l
∗ and stop; the optimal resource allocation is u
∗
=
[
u
1
∗
,
u
2
∗
,
…
,
u
m
∗
].
Ifs
[
l
]
<
g
(
u
¯
), go to Step 6.
Step 6. Set u
[
l
]
∗
=
u
¯, U
=
U
+
u
[
l
]
∗, C
′
=
C
′
-
s
′
∑
i
=
l
m
‍
∏
j
=
1
n
i
‍
(
1
+
B
p
[
i
]
[
j
]
f
[
i
]
(
j
)
), and l
=
l
+
1. If l
>
m, then stop; there is no feasible solution; else go to Step 4.For the problem1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
-
B
t
)
f
i
(
r
), G
T, C
m
a
x
≤
C
∣
∑
‍
u
j, if we only allocate the resource to the setup time of group G
m and for the groups scheduled before it the resource allocation amount is 0, then according to (7), we have(27)
C
=
s
∑
i
=
1
m
-
1
‍
∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
1
-
B
p
l
j
f
l
j
+
s
m
∏
j
=
1
n
m
‍
1
-
B
p
m
j
f
m
j
-
A
B
∏
i
=
1
m
‍
∏
j
=
1
n
i
‍
1
-
B
p
i
j
f
i
j
+
A
B
=
s
∑
i
=
1
m
-
1
‍
∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
1
-
B
p
l
j
f
l
j
+
s
m
∏
j
=
1
n
m
‍
1
-
B
p
m
j
f
m
j
+
K
,where s
=
g
(
0
) and K
=
A
/
B
-
(
A
/
B
)
∏
i
=
1
m
‍
∏
j
=
1
n
i
‍
1
-
B
p
[
i
]
[
j
]
f
[
i
]
(
j
). Hence(28)
s
m
=
C
-
K
-
s
∑
i
=
1
m
-
1
‍
∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
1
-
B
p
l
j
f
l
j
∏
j
=
1
n
m
‍
1
-
B
p
m
j
f
m
j
.Ifs
[
m
]
≥
g
(
0
), then the constraint C
m
a
x
≤
C can be satisfied even if the resource allocation amount u
[
m
] of G
[
m
] is 0. And we do not have to allocate the resource to the groups; stop.Ifg
(
u
¯
)
≤
s
[
m
]
<
g
(
0
), then the optimal resource allocation is u
[
m
]
∗
=
g
-
1
(
s
[
m
]
), u
[
j
]
∗
=
0, j
=
1,2
,
…
,
m
-
1.Ifs
[
m
]
<
g
(
u
¯
), then the optimal resource allocation of group G
[
m
] should be u
¯; that is, u
[
m
]
∗
=
u
¯. And the optimal resource consumption u
[
j
]
∗, j
=
1,2
,
…
,
m
-
1, can be calculated by the same method.Based on the above analysis, we propose an algorithm to solve the problem1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
-
B
t
)
f
i
(
r
), G
T, C
m
a
x
≤
C
∣
∑
‍
u
j.Algorithm 11.
We have the following.
Step 1. Jobs in each group are scheduled in nondecreasing order of p
i
j; that is,(29)
p
i
1
≤
p
i
2
≤
⋯
≤
p
i
n
i
,
i
=
1,2
,
…
,
m
.
Step 2. Groups are scheduled in nonincreasing order of ρ
G
[
i
]
=
∏
j
=
1
n
i
‍
(
1
-
B
p
[
i
]
[
j
]
f
[
i
]
(
j
)
); that is,(30)
ρ
G
1
≥
ρ
G
2
≥
⋯
≥
ρ
G
m
.
Step 3. For the obtained schedule π
=
[
G
[
1
]
,
G
[
2
]
,
…
,
G
[
m
]
], set u
[
i
]
∗
=
0  (
i
=
1,2
,
…
,
m
), U
=
0, s
=
g
(
0
), s
′
=
g
(
u
¯
), l
=
m, and C
′
=
C
-
K.
Step 4. Calculate(31)
s
l
=
C
′
-
s
∑
i
=
1
l
-
1
‍
∏
l
=
i
m
‍
∏
j
=
1
n
l
‍
1
-
B
p
l
j
f
l
j
∏
i
=
l
m
‍
∏
j
=
1
n
i
‍
1
-
B
p
i
j
f
i
j
.If l
=
0, stop; else go to Step 5.
Step 5. If s
[
l
]
≥
g
(
0
), stop.
Ifg
(
u
¯
)
≤
s
[
l
]
<
g
(
0
), set u
[
l
]
∗
=
g
-
1
(
s
[
l
]
) and U
=
U
+
u
[
l
]
∗ and stop; the optimal resource allocation is u
∗
=
[
u
[
1
]
∗
,
u
[
2
]
∗
,
…
,
u
[
m
]
∗
].
Ifs
[
l
]
<
g
(
u
¯
), go to Step 6.
Step 6. Set u
[
l
]
∗
=
u
¯, U
=
U
+
u
[
l
]
∗, C
′
=
C
′
-
s
′
∑
i
=
l
m
‍
∏
j
=
1
n
i
‍
(
1
-
B
p
[
i
]
[
j
]
f
[
i
]
(
j
)
), and l
=
l
-
1. If l
<
1, then stop; there is no feasible solution; else go to Step 4.Obviously, the time for Steps 1 and 2 isO
(
n
l
o
g
n
). If we are able to calculate all the values of g and g
-
1 in Algorithm 10 in O
(
h
(
n
)
) time, then the total time for Algorithm 10 (Algorithm 11) is O
(
m
a
x
{
n
h
(
n
)
,
n
l
o
g
n
}
) time.The following example is used to illustrate Algorithm10.Example 12.
Considern
=
6, m
=
3, f
i
(
r
)
=
r
a
i, and g
(
u
i
)
=
26
-
2
u
i. The normal processing times p
i
j and a
i for each group are the same as Table 1, A
=
1, B
=
0.1, u
¯
=
10, and C
=
3000.Solution. According to Algorithm 10, we solve Example 12 as follows.Steps 1, 2, and 3. Similar to Example 9, the obtained schedule is [
J
31
→
J
32
]
→
[
J
22
→
J
21
]
→
[
J
12
→
J
11
]. Set u
i
∗
=
0  (
i
=
1,2
,
…
,
m
), U
=
0, s
=
g
(
0
)
=
26, s
′
=
g
(
u
¯
)
=
6, l
=
1, K
=
1284.072, and C
′
=
C
-
K
=
3000
-
1284.072
=
1715.928.Step 4. Calculate(32)
s
1
=
s
3
=
C
′
-
s
∑
i
=
l
+
1
m
‍
∏
k
=
i
m
‍
∏
j
=
1
n
k
‍
1
+
B
p
k
j
f
k
j
∏
i
=
l
m
‍
∏
j
=
1
n
i
‍
1
+
B
p
i
j
f
i
j
=
8.6391
.Steps 5 and 6. Consider 6
<
8.6391
<
26, u
3
∗
=
g
-
1
(
8.6391
)
=
8.6805, U
=
U
+
u
3
∗
=
8.6805, C
′
=
C
′
-
s
′
∑
i
=
l
m
‍
∏
j
=
1
n
i
‍
(
1
+
B
p
[
i
]
[
j
]
f
[
i
]
(
j
)
)
=
1577.935, and l
=
2.Similarlys
[
2
]
=
s
2
=
76.72711
>
26; stop. Hence, u
3
∗
=
8.6805, u
2
∗
=
u
1
∗
=
0, and U
=
10.Therefore, the optimal schedule is[
J
31
→
J
32
]
→
[
J
22
→
J
21
]
→
[
J
12
→
J
11
], and the optimal completion times are calculated as follows:(33)
s
3
=
8.6391
,
C
31
=
8.6391
+
15
∗
1
+
0.1
∗
8.6391
∗
1
-
0.1
=
36.5978
,
C
32
=
36.5978
+
18
∗
1
+
0.1
∗
36.5978
∗
2
-
0.1
=
114.8569
,
s
2
=
26
,
C
22
=
114.8569
+
26
+
10
∗
1
+
0.1
∗
114.8569
+
26
∗
1
-
0.3
=
291.7138
,
C
21
=
291.7138
+
20
∗
1
+
0.1
∗
291.7138
∗
2
-
0.3
=
781.8493
,
s
1
=
26
,
C
12
=
781.8493
+
26
+
8
∗
1
+
0.1
∗
781.8493
+
26
∗
1
-
0.2
=
1462.129
,
C
11
=
1462.129
+
12
∗
1
+
0.1
∗
1462.129
∗
2
-
0.2
≈
3000
.


## 5. Conclusions

We considered some single-machine group scheduling problems with general position-dependent learning effects and deteriorating jobs simultaneously. It is assumed that group setup time of a group is a positive strictly decreasing continuous function of the amount of consumed resource. For the resource constrained problems1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
±
B
t
)
f
i
(
r
), G
T, ∑
j
=
1
n
‍
u
j
≤
U
∣
C
m
a
x and 1
∣
s
i
=
g
(
u
i
), p
i
j
r
(
t
)
=
p
i
j
(
A
±
B
t
)
f
i
(
r
), G
T, C
m
a
x
≤
C
∣
∑
‍
u
j, we showed that they can be solved in polynomial time under the proposed model.



---

*Source: 758919-2015-07-27.xml*