# Maximum Lateness Scheduling on Two-Person Cooperative Games with Variable Processing Times and Common Due Date

Authors: Peng Liu; Xiaoli Wang
Journal: Journal of Optimization
 (2017)

---

## Abstract

A new maximum lateness scheduling model in which both cooperative games and variable processing times exist simultaneously is considered in this paper. The job variable processing time is described by an increasing or a decreasing function dependent on the position of a job in the sequence. Two persons have to cooperate in order to process a set of jobs. Each of them has a single machine and their processing cost is defined as the minimum value of maximum lateness. All jobs have a common due date. The objective is to maximize the multiplication of their rational positive cooperative profits. A division of those jobs should be negotiated to yield a reasonable cooperative profit allocation scheme acceptable to them. We propose the sufficient and necessary conditions for the problems to have positive integer solution.


---

## Body

## 1. Introduction

In this paper, we introduce a new maximum lateness scheduling model in which both cooperative games and variable processing times exist simultaneously. There are many situations where one person is not able to undertake all the jobs alone in a large project and two persons need to cooperate in order to complete a project. Each person offers a single machine to process jobs. A division of those jobs should be negotiated to yield a reasonable cooperative profit allocation scheme acceptable to them. In many manufacturing processes, the processing times of jobs may be dependent on their positions in the sequence. This phenomenon is called“aging effect” or“learning effect” in the literature. In the aging effect, the processing time of a job increases as a function of its position in the sequence, while, in the learning effect, the processing time of a job decreases as a function of its position in the sequence. In this paper, we address maximum lateness scheduling on two-person cooperative games with variable processing times. To the best of our knowledge, no work has been done on maximum lateness scheduling models combining two aspects of cooperative games and variable processing times.Scheduling problems with two-person cooperative games have received increasing attention in recent years. Jin et al. [1] consider the two-person cooperative games on makespan scheduling. The case of jobs with same processing time is addressed and each party’s processing cost is determined by their minimized makespan. Dou et al. [2] consider the two-person cooperative games on total completion time scheduling where the processing time of each job is the same. Gu et al. [3] discuss the two-person Nash Bargaining problem with changeable processing time, where the processing cost is defined as their minimized maximum flow time. Jin [4] establishes a mathematical model of the problem where two persons process a batch of jobs by cooperation, where job processing time is a linear function of its starting time. Jin [5] studies two-person cooperative games problem on total completion time scheduling with changeable processing time. Gu et al. [6] consider the scheduling problem on two-person cooperative games, where the processing cost is defined as their minimized maximum latency. Liu et al. [7] study the problem of two-person cooperative games on minimizing the total (weighted) number of tardy jobs and on minimizing the total (weighted) completion time. Chen [8] studies an integer-valued cooperative games model on scheduling. Tang et al. [9] propose a new topic on dual relationships between job games and machine games and provide the extensive reviews of research on scheduling games. The literature mentioned above investigates the cooperative games on scheduling; however, they do not consider the maximum lateness scheduling with variable processing times.Next, we will present a brief review of scheduling problems with variable processing times as follows. Gawiejnowicz [10] is the first time to introduce the position dependent on a number of executed jobs on a single processor. Biskup [11] is the first to consider the learning effect in a scheduling problem. Cheng and Wang [12] consider a single machine scheduling problem in which the job processing times will decrease as a result of learning. Mosheiov [13] proves that flow-time minimization with a learning effect on parallel identical machines has a polynomial time solution. Bachman and Janiak [14] investigate some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. Liu et al. [15] consider the single machine scheduling problems with two agents and position-dependent processing times. Rudek [16] provides the computational complexity results of scheduling problems with position-dependent job processing times, where the boundary between polynomially solvable and strongly NP-hard cases is given. J. B. Wang and J. J. Wang [17] investigate flowshop scheduling problems with a general exponential learning effect. Zhou and Zhang [18] consider the cooperative games based on multiple-machine scheduling problems with learning effects. Zhang et al. [19] propose a group scheduling model with deteriorating and learning effect on a single machine. The aging effect is mentioned for the first time by Mosheiov [13] during analysis of the learning effect. Janiak and Rudek [20] prove that the makespan minimization problems on a single machine with release dates and some special cases of the given aging effect are NP-hard. Yang et al. [21] consider single machine scheduling and slack due date assignment problems simultaneously with the position-dependent aging effect and deteriorating maintenance. Rudek [22] analyzes the single machine maximum lateness minimization scheduling problem with processing time-based aging effects. Ji et al. [23] consider a single machine due date assignment scheduling problem with job-dependent aging effects and a deteriorating maintenance activity. Choi [24] considers a two-agent single machine scheduling problem with linear position-based aging effects and job-dependent aging ratios. Zeng et al. [25] consider the problem of bidirectional nonnegative deep model and its optimization in learning. The difference between our model and the above scheduling models is that we incorporate the important factor of cooperative games in the model.The remainder of this paper is organized as follows. In Section2, we describe the proposed problems. In Section 3, we discuss the two-person cooperative games on maximum lateness scheduling problems with an aging effect and a learning effect, respectively. Section 4 gives some concluding remarks.


## 2. Problem Description

The problems of maximum lateness scheduling on two-person cooperative games with variable processing times are described as follows. There is a set of jobsJ=J1,J2,…,Jn that has to be processed by two persons. Each job should be processed only once without interruption. All jobs are available for processing at time zero. Two persons, each with a single machine, cooperate to complete the processing of these n jobs. The due date of each job is denoted by dj, and all jobs have a common due date d; that is, dj=d. The processing time pj,r of job Jj is a function dependent on its position r in a sequence. We consider two special models of job variable processing times: (1) anaging effectpj,r=P0+ar and (2) alearning effectpj,r=P0-ar, j=1,2,…,n, r=1,2,…,n, where P0 is the normal processing time, a>0 denotes a constantaging ratio in model (1) and a constantlearning ratio in model (2). Since job processing time is positive value, it is assumed that a<P0/n for the learning effect model. The normal processing time and theaging/learning ratioare identical for all jobs.Given a solution for the two-person cooperative games, we useCj to denote the completion time for job Jj. If we use X1 and X2 to denote each person’s subset of jobs, then X1∪X2=J, X1∩X2=⌀. For person ii=1,2, processing a job per unit time will bring bii=1,2 unit profit; the processing cost is defined as the minimum value of the maximum lateness of jobs, that is, min Lmaxi=min⁡max⁡Cj-d∣j∈Xi, and then the profit function of person i is defined by ui=bi∑j∈Xipj,r-min⁡Lmaxi. If two persons cannot achieve a cooperation agreement, let ei denote the ith individual’s cost; then there should be the inequalities of the form ei≥uiϕ=0, (i=1,2). Hence, the cooperative profit of person i is formulated by vi=uiXi-ei=bi∑j∈Xipj,r-min⁡Lmaxi-ei, the overall profit of two persons is measured by the product of v1 and v2, and our objective is to maximize this product.The problems of maximum lateness scheduling on two-person cooperative games with variable processing times and common due date can be described by the three-field notation of Jin et al. [1] of the forms G2pj,r=P0+ar,dj=dv1v2/Lmax and G2pj,r=P0-ar,dj=dv1v2/Lmax, respectively. The first-field G2 represents two-person cooperative games and each person has one machine. The second field describes job characteristics, that is, the structures of the processing time and the due date. The third field v1v2/Lmax represents the optimization goal.


## 3. Main Results

We consider the two-person cooperative games on maximum lateness scheduling problemsG2pj,r=P0+ar,dj=dv1v2/Lmax and G2pj,r=P0-ar,dj=dv1v2/Lmax in Sections 3.1 and 3.2, respectively.


### 3.1. ProblemG2pj,r=P0+ar,dj=dv1v2/Lmax

Letk be the number of jobs in subset X1 assigned to person 1, and let n-k be the number of jobs in subset X2 assigned to person 2, 1≤k≤n-1. Next, we will show that Ck=kP0+k(k+1)/2a for person 1 by induction.(1)C1=p1,1=P0+a=P0+1×1+12a.C2=C1+p2,2=P0+a+P0+2a=2P0+2×2+12a.Suppose Cj=jP0+jj+1/2a for job Jj; then we consider job Jj+1:(2)Cj+1=Cj+pj+1,j+1=jP0+jj+12a+P0+aj+1=j+1P0+j+1j+22a.Hence, we proveCk=kP0+k(k+1)/2a, which is a fixed constant for all permutations of the jobs.Likewise, we can show thatCn=(n-k)P0+(n-k)(n-k+1)/2a for person 2 by induction. Cn=n-kP0+1+2+⋯+n-ka=n-kP0+(n-k)(n-k+1)/2a, which is a fixed constant for all permutations of the jobs. (3)L1max=max⁡Cj-dj∣j∈X1=max⁡jP0+jj+12a-dj∣j∈X1=max⁡P0+a-d,2P0+2×2+12a-d,…,kP0+kk+12a-d=kP0+kk+12a-d,L2max=max⁡Cj-dj∣j∈X2=n-kP0+n-kn-k+12a-d.The profit functions are as follows:(4)u1X1=b1∑j∈X1pj,r-min⁡Lmax1=b1Ck-min⁡Lmax1=b1-1kP0+kk+12a+d,u2X2=b2∑j∈X2pj,r-min⁡Lmax2=b2-1n-kP0+n-kn-k+12a+d.Since the profit functions have positive values, it should hold that bi>1, i=1,2.Thus, the two cooperative profit functions are the quadratic functions of positive integerk of the form(5)v1k=u1X1-e1=b1-1kP0+kk+12a+d-e1=ab1-12k2+1+2P0ak+2d-e1ab1-1,v2k=u2X2-e2=b2-1n-kP0+n-kn-k+12a+d-e2=ab2-12k2-1+2n+2P0ak+n2+n+2nP0a+2d-e2ab2-1.When the discriminantΔ1=1+2P0/a2-8(d-e1)/a(b1-1) of v1 and the discriminant Δ2=2P0/a+12-8(d-e2)/a(b2-1) of v2 are smaller than zero, we do not need to study this problem. So we only consider the solution when (6)Δi≥0,ei≥0,bi>1,i=1,2,a>0,1≤k≤n-1.Under the condition ofΔi≥0, v1kv2k can be expressed as the following form: (7)v1kv2k=a2b1-1b2-14k-α1k-α2k-α3k-α4,where(8)α1=-12+P0a-12+P0a2-2d-e1ab1-1,α2=-12+P0a+12+P0a2-2d-e1ab1-1,α3=n+12+P0a-12+P0a2-2d-e2ab2-1,α4=n+12+P0a+12+P0a2-2d-e2ab2-1.Theorem 1.
The sufficient and necessary condition for the problemG2pj,r=P0+ar,dj=dv1v2/Lmax to have positive integer solution k is (9)β1≤β2.Furthermore, if the problem has a solution, then the optimal solution k∗ is certainly in closed interval β1,β2, where β1=α2+1, β2=α3-1.Proof.
If the problem has a solution, the two cooperative profit functionsv1 and v2 must be of positive value. We have k<α1 and k>α2 from v1>0. We obtain k<α3 and k>α4 from v2>0. Since α1<0, α4>n, and 1≤k≤n-1, we have α2<k<α3. Hence, we have k∈α2,α3∩1,n-1. Since k is a integer, we set β1=α2+1, β2=α3-1. Thus, 1≤β1≤n-1, 1≤β2≤n-1. So the problem G2pj,r=P0+ar,dj=dv1v2/Lmax to have a solution equivalent to the closed interval β1,β2 has at least one positive integer k, that is, β1≤β2. Therefore, the sufficient and necessary condition for the problem G2pj,r=P0+ar,dj=dv1v2/Lmax to have positive integer solution k is β1≤β2.
We setv1(x)·v2(x) as a four-time polynomial in x and the function can be expressed as v1x·v2x=a2(b1-1)(b2-1)/4x-α1x-α2x-α3x-α4. So v1x·v2x′=0 is a cubic polynomial in x and v1x·v2x′=0 have three roots. Under the conditions of (6) and (9), we know that there are three roots to v1k·v2k′=0. Without loss of generality, let us set them to be δ1,δ2,δ3 and their relationship can be defined as δ1<δ2<δ3. So δ1, δ2, and δ3 are the three extreme points of v1(k)·v2(k) and we can get β1≤δ2≤β2. Since the coefficient of four times polynomial about expression (7) is positive, the coefficient of cubic polynomial v1k·v2k′ is positive and δ2 is the only extreme point and maximum value point. Therefore, the optimal solution k∗ of the problem G2pj,r=P0+ar,dj=dv1v2/Lmax is certainly in closed interval β1,β2.We have the following theorem from Theorem1.Theorem 2.
Under the condition of expression (9), there is an optimal solution k∗ for the problem G2pj,r=P0+ar,dj=dv1v2/Lmax, and the result can be expressed as k∗=δ2 or δ2. The optimal solution k∗ is as follows:(I)
Ifδ2∈[β1,β2] and δ2∉[β1,β2], then k∗=δ2;(II)
Ifδ2∈[β1,β2] and δ2∉[β1,β2], then k∗=δ2;(III)
Ifδ2∈[β1,β2] and δ2∈[β1,β2],
whenv1δ2·v2δ2≤v1δ2·v2δ2, k∗=δ2;whenv1δ2·v2δ2≥v1δ2·v2δ2, k∗=δ2.Remark 3.
The problem size isO(1) and the optimal solution can also be found in a constant time O(1).
Furthermore, we consider the following numerical example.Example 4.
For the problemG2pj,r=P0+ar,dj=dv1v2/Lmax, we assume that P0=1, a=1, d=11, b1=2, b2=3, e1=11, e2=10, and n=5.Solution. The two cooperative profit functions are (10)v1k=ab1-12k2+1+2P0ak+2d-e1ab1-1=12k2+32k,v2k=ab2-12k2-1+2n+2P0ak+n2+n+2nP0a+2d-e2ab2-1=k2-13k+41.We haveΔ1=9/4>0, Δ2=5>0, α1=-3, α2=0, α3=5.382, and α4=7.618. So we obtain β1=α2+1=1, β2=α3-1=5. Three roots to v1k·v2k′=0 are δ1=-1.768, δ2=2.613, and δ3=6.656, respectively. So we obtain k∗=δ2=2 or k∗=δ2=3. Because v12·v22=94.978<v13·v23=98.9604, we have k∗=3.


### 3.2. ProblemG2pj,r=P0-ar,dj=dv1v2/Lmax

For the problemG2pj,r=P0-ar,dj=dv1v2/Lmax, we can calculate similarly the makespan for persons 1 and 2 by induction.C
k
=
k
P
0
-
k
(
k
+
1
)
/
2
a, which is a fixed constant for all permutations of the jobs.C
n
=
(
n
-
k
)
P
0
-
(
n
-
k
)
(
n
-
k
+
1
)
/
2
a, which is a fixed constant for all permutations of the jobs.(11)L1max=max⁡Cj-dj∣j∈X1=max⁡jP0-jj+12a-dj∣j∈X1=max⁡P0-a-d,2P0-2×2+12a-d,…,kP0-kk+12a-d=kP0-kk+12a-d,L2max=max⁡Cj-dj∣j∈X2=n-kP0-n-kn-k+12a-d.The profit functions are as follows.(12)u1X1=b1∑j∈X1pj,r-min⁡Lmax1=b1Ck-min⁡Lmax1=b1-1kP0-kk+12a+d,u2X2=b2∑j∈X2pj,r-min⁡Lmax2=b2-1n-kP0-n-kn-k+12a+d.Since the profit functions have positive values, it should hold that bi>1, i=1,2.Thus, the two cooperative profit functions are the quadratic functions of positive integerk of the form(13)v1k=u1X1-e1=b1-1kP0-kk+12a+d-e1=-ab1-12k2-2P0a-1k-2d-e1ab1-1,v2k=u2X2-e2=b2-1n-kP0-n-kn-k+12a+d-e2=-ab2-12k2-1+2n-2P0ak+n2+n-2nP0a-2d-e2ab2-1.Since the profit functions have positive values, it should hold that bi>1, i=1,2.When the discriminantΔ1=2P0/a-12+8(d-e1)/a(b1-1) of v1 and the discriminant Δ2=2P0/a-12+8(d-e2)/a(b2-1) of v2 are smaller than zero, we do not need to study this problem. So we only consider the solution when(14)Δi≥0,ei≥0,bi>1,i=1,2,0<a<P0n,1≤k≤n-1.Under the condition ofΔi≥0, v1kv2k can be expressed as the following form: (15)v1kv2k=a2b1-1b2-14k-γ1k-γ2k-γ3k-γ4,where(16)γ1=P0a-12-P0a-122+2d-e1ab1-1,γ2=P0a-12+P0a-122+2d-e1ab1-1,γ3=n+12-P0a-P0a-122+2d-e2ab2-1,γ4=n+12-P0a+P0a-122+2d-e2ab2-1.In consideration of clear expression, we setγ5=P0/a-1/2, γ6=n+1/2-P0/a.Theorem 5.
The sufficient and necessary condition for the problemG2pj,r=P0-ar,dj=dv1v2/Lmax to have positive integer solution k is (17)ηl≤ηm.Furthermore, if the problem has a solution, then the optimal solution k∗ is certainly in closed interval ηl,ηm, where ηl=max⁡{ηl1,ηl2}, ηm=min⁡{ηm1,ηm2}, ηl1=γ1+1, ηl2=γ6+1, ηm1=γ5-1, and ηm2=γ4-1.Proof.
If the problem has a solution, the two cooperative profit functionsv1 and v2 must be of positive value. We have γ1<k<γ2 from v1>0. Since 0<a<P0/n, we have k<P0/a-1/2; that is, k<γ5. Then, we know γ5<γ2 through the comparing between γ2 and γ5. So we have γ1<k<γ5.
We getγ3<k<γ4 from v2>0. Because k-1/2-n+P0/a>0, so we have k>γ6. Since γ3<γ6, then we have γ6<k<γ4.
Thus, we obtainγ1<k<γ5 and γ6<k<γ4. Since 1≤k≤n-1 andk is a integer, so we set ηl1=γ1+1, ηl2=γ6+1, ηm1=γ5-1, ηm2=γ4-1, ηl=max⁡{ηl1,ηl2}, and ηm=min{ηm1,ηm2}. Then we obtain 0≤γ1<n-1, 1≤γ4<n, 1≤γ5<n, 1≤γ6<n, and n≥2 from the expressions of γ1, γ4, γ5, and γ6. Hence, 1≤ηl≤n-1, 1≤ηm≤n-1. Therefore, the sufficient and necessary condition for the problem G2pj,r=P0-ar,dj=dv1v2/Lmax to have integer solution k is ηl≤ηm. Similarly, we can prove that the optimal solution k∗ is certainly in closed interval ηl,ηm.We have the following Theorem6 that is similar to Theorem 2. If we prove ξ2∈ηl,ηm, we obtain that ξ2 is the only extreme point of v1(x)·v2(x) in ηl,ηm and it is also the maximum value point of v1(x)·v2(x).Theorem 6.
Under the condition of expression (17), there is an optimal solution k∗ for the problem G2pj,r=P0-ar,dj=dv1v2/Lmax, and the result can be expressed as k∗=ξ2 or ξ2. The optimal solution k∗ is as follows: (I)
Ifξ2∈[ηl,ηm] and ξ2∉[ηl,ηm], then k∗=ξ2;(II)
Ifξ2∈[ηl,ηm] and ξ2∉[ηl,ηm], then k∗=ξ2;(III)
Ifξ2∈[ηl,ηm] and ξ2∈[ηl,ηm],
whenv1ξ2·v2ξ2≤v1ξ2·v2ξ2, then k∗=ξ2;whenv1ξ2·v2ξ2≥v1ξ2·v2ξ2, then k∗=ξ2.


## 3.1. ProblemG2pj,r=P0+ar,dj=dv1v2/Lmax

Letk be the number of jobs in subset X1 assigned to person 1, and let n-k be the number of jobs in subset X2 assigned to person 2, 1≤k≤n-1. Next, we will show that Ck=kP0+k(k+1)/2a for person 1 by induction.(1)C1=p1,1=P0+a=P0+1×1+12a.C2=C1+p2,2=P0+a+P0+2a=2P0+2×2+12a.Suppose Cj=jP0+jj+1/2a for job Jj; then we consider job Jj+1:(2)Cj+1=Cj+pj+1,j+1=jP0+jj+12a+P0+aj+1=j+1P0+j+1j+22a.Hence, we proveCk=kP0+k(k+1)/2a, which is a fixed constant for all permutations of the jobs.Likewise, we can show thatCn=(n-k)P0+(n-k)(n-k+1)/2a for person 2 by induction. Cn=n-kP0+1+2+⋯+n-ka=n-kP0+(n-k)(n-k+1)/2a, which is a fixed constant for all permutations of the jobs. (3)L1max=max⁡Cj-dj∣j∈X1=max⁡jP0+jj+12a-dj∣j∈X1=max⁡P0+a-d,2P0+2×2+12a-d,…,kP0+kk+12a-d=kP0+kk+12a-d,L2max=max⁡Cj-dj∣j∈X2=n-kP0+n-kn-k+12a-d.The profit functions are as follows:(4)u1X1=b1∑j∈X1pj,r-min⁡Lmax1=b1Ck-min⁡Lmax1=b1-1kP0+kk+12a+d,u2X2=b2∑j∈X2pj,r-min⁡Lmax2=b2-1n-kP0+n-kn-k+12a+d.Since the profit functions have positive values, it should hold that bi>1, i=1,2.Thus, the two cooperative profit functions are the quadratic functions of positive integerk of the form(5)v1k=u1X1-e1=b1-1kP0+kk+12a+d-e1=ab1-12k2+1+2P0ak+2d-e1ab1-1,v2k=u2X2-e2=b2-1n-kP0+n-kn-k+12a+d-e2=ab2-12k2-1+2n+2P0ak+n2+n+2nP0a+2d-e2ab2-1.When the discriminantΔ1=1+2P0/a2-8(d-e1)/a(b1-1) of v1 and the discriminant Δ2=2P0/a+12-8(d-e2)/a(b2-1) of v2 are smaller than zero, we do not need to study this problem. So we only consider the solution when (6)Δi≥0,ei≥0,bi>1,i=1,2,a>0,1≤k≤n-1.Under the condition ofΔi≥0, v1kv2k can be expressed as the following form: (7)v1kv2k=a2b1-1b2-14k-α1k-α2k-α3k-α4,where(8)α1=-12+P0a-12+P0a2-2d-e1ab1-1,α2=-12+P0a+12+P0a2-2d-e1ab1-1,α3=n+12+P0a-12+P0a2-2d-e2ab2-1,α4=n+12+P0a+12+P0a2-2d-e2ab2-1.Theorem 1.
The sufficient and necessary condition for the problemG2pj,r=P0+ar,dj=dv1v2/Lmax to have positive integer solution k is (9)β1≤β2.Furthermore, if the problem has a solution, then the optimal solution k∗ is certainly in closed interval β1,β2, where β1=α2+1, β2=α3-1.Proof.
If the problem has a solution, the two cooperative profit functionsv1 and v2 must be of positive value. We have k<α1 and k>α2 from v1>0. We obtain k<α3 and k>α4 from v2>0. Since α1<0, α4>n, and 1≤k≤n-1, we have α2<k<α3. Hence, we have k∈α2,α3∩1,n-1. Since k is a integer, we set β1=α2+1, β2=α3-1. Thus, 1≤β1≤n-1, 1≤β2≤n-1. So the problem G2pj,r=P0+ar,dj=dv1v2/Lmax to have a solution equivalent to the closed interval β1,β2 has at least one positive integer k, that is, β1≤β2. Therefore, the sufficient and necessary condition for the problem G2pj,r=P0+ar,dj=dv1v2/Lmax to have positive integer solution k is β1≤β2.
We setv1(x)·v2(x) as a four-time polynomial in x and the function can be expressed as v1x·v2x=a2(b1-1)(b2-1)/4x-α1x-α2x-α3x-α4. So v1x·v2x′=0 is a cubic polynomial in x and v1x·v2x′=0 have three roots. Under the conditions of (6) and (9), we know that there are three roots to v1k·v2k′=0. Without loss of generality, let us set them to be δ1,δ2,δ3 and their relationship can be defined as δ1<δ2<δ3. So δ1, δ2, and δ3 are the three extreme points of v1(k)·v2(k) and we can get β1≤δ2≤β2. Since the coefficient of four times polynomial about expression (7) is positive, the coefficient of cubic polynomial v1k·v2k′ is positive and δ2 is the only extreme point and maximum value point. Therefore, the optimal solution k∗ of the problem G2pj,r=P0+ar,dj=dv1v2/Lmax is certainly in closed interval β1,β2.We have the following theorem from Theorem1.Theorem 2.
Under the condition of expression (9), there is an optimal solution k∗ for the problem G2pj,r=P0+ar,dj=dv1v2/Lmax, and the result can be expressed as k∗=δ2 or δ2. The optimal solution k∗ is as follows:(I)
Ifδ2∈[β1,β2] and δ2∉[β1,β2], then k∗=δ2;(II)
Ifδ2∈[β1,β2] and δ2∉[β1,β2], then k∗=δ2;(III)
Ifδ2∈[β1,β2] and δ2∈[β1,β2],
whenv1δ2·v2δ2≤v1δ2·v2δ2, k∗=δ2;whenv1δ2·v2δ2≥v1δ2·v2δ2, k∗=δ2.Remark 3.
The problem size isO(1) and the optimal solution can also be found in a constant time O(1).
Furthermore, we consider the following numerical example.Example 4.
For the problemG2pj,r=P0+ar,dj=dv1v2/Lmax, we assume that P0=1, a=1, d=11, b1=2, b2=3, e1=11, e2=10, and n=5.Solution. The two cooperative profit functions are (10)v1k=ab1-12k2+1+2P0ak+2d-e1ab1-1=12k2+32k,v2k=ab2-12k2-1+2n+2P0ak+n2+n+2nP0a+2d-e2ab2-1=k2-13k+41.We haveΔ1=9/4>0, Δ2=5>0, α1=-3, α2=0, α3=5.382, and α4=7.618. So we obtain β1=α2+1=1, β2=α3-1=5. Three roots to v1k·v2k′=0 are δ1=-1.768, δ2=2.613, and δ3=6.656, respectively. So we obtain k∗=δ2=2 or k∗=δ2=3. Because v12·v22=94.978<v13·v23=98.9604, we have k∗=3.


## 3.2. ProblemG2pj,r=P0-ar,dj=dv1v2/Lmax

For the problemG2pj,r=P0-ar,dj=dv1v2/Lmax, we can calculate similarly the makespan for persons 1 and 2 by induction.C
k
=
k
P
0
-
k
(
k
+
1
)
/
2
a, which is a fixed constant for all permutations of the jobs.C
n
=
(
n
-
k
)
P
0
-
(
n
-
k
)
(
n
-
k
+
1
)
/
2
a, which is a fixed constant for all permutations of the jobs.(11)L1max=max⁡Cj-dj∣j∈X1=max⁡jP0-jj+12a-dj∣j∈X1=max⁡P0-a-d,2P0-2×2+12a-d,…,kP0-kk+12a-d=kP0-kk+12a-d,L2max=max⁡Cj-dj∣j∈X2=n-kP0-n-kn-k+12a-d.The profit functions are as follows.(12)u1X1=b1∑j∈X1pj,r-min⁡Lmax1=b1Ck-min⁡Lmax1=b1-1kP0-kk+12a+d,u2X2=b2∑j∈X2pj,r-min⁡Lmax2=b2-1n-kP0-n-kn-k+12a+d.Since the profit functions have positive values, it should hold that bi>1, i=1,2.Thus, the two cooperative profit functions are the quadratic functions of positive integerk of the form(13)v1k=u1X1-e1=b1-1kP0-kk+12a+d-e1=-ab1-12k2-2P0a-1k-2d-e1ab1-1,v2k=u2X2-e2=b2-1n-kP0-n-kn-k+12a+d-e2=-ab2-12k2-1+2n-2P0ak+n2+n-2nP0a-2d-e2ab2-1.Since the profit functions have positive values, it should hold that bi>1, i=1,2.When the discriminantΔ1=2P0/a-12+8(d-e1)/a(b1-1) of v1 and the discriminant Δ2=2P0/a-12+8(d-e2)/a(b2-1) of v2 are smaller than zero, we do not need to study this problem. So we only consider the solution when(14)Δi≥0,ei≥0,bi>1,i=1,2,0<a<P0n,1≤k≤n-1.Under the condition ofΔi≥0, v1kv2k can be expressed as the following form: (15)v1kv2k=a2b1-1b2-14k-γ1k-γ2k-γ3k-γ4,where(16)γ1=P0a-12-P0a-122+2d-e1ab1-1,γ2=P0a-12+P0a-122+2d-e1ab1-1,γ3=n+12-P0a-P0a-122+2d-e2ab2-1,γ4=n+12-P0a+P0a-122+2d-e2ab2-1.In consideration of clear expression, we setγ5=P0/a-1/2, γ6=n+1/2-P0/a.Theorem 5.
The sufficient and necessary condition for the problemG2pj,r=P0-ar,dj=dv1v2/Lmax to have positive integer solution k is (17)ηl≤ηm.Furthermore, if the problem has a solution, then the optimal solution k∗ is certainly in closed interval ηl,ηm, where ηl=max⁡{ηl1,ηl2}, ηm=min⁡{ηm1,ηm2}, ηl1=γ1+1, ηl2=γ6+1, ηm1=γ5-1, and ηm2=γ4-1.Proof.
If the problem has a solution, the two cooperative profit functionsv1 and v2 must be of positive value. We have γ1<k<γ2 from v1>0. Since 0<a<P0/n, we have k<P0/a-1/2; that is, k<γ5. Then, we know γ5<γ2 through the comparing between γ2 and γ5. So we have γ1<k<γ5.
We getγ3<k<γ4 from v2>0. Because k-1/2-n+P0/a>0, so we have k>γ6. Since γ3<γ6, then we have γ6<k<γ4.
Thus, we obtainγ1<k<γ5 and γ6<k<γ4. Since 1≤k≤n-1 andk is a integer, so we set ηl1=γ1+1, ηl2=γ6+1, ηm1=γ5-1, ηm2=γ4-1, ηl=max⁡{ηl1,ηl2}, and ηm=min{ηm1,ηm2}. Then we obtain 0≤γ1<n-1, 1≤γ4<n, 1≤γ5<n, 1≤γ6<n, and n≥2 from the expressions of γ1, γ4, γ5, and γ6. Hence, 1≤ηl≤n-1, 1≤ηm≤n-1. Therefore, the sufficient and necessary condition for the problem G2pj,r=P0-ar,dj=dv1v2/Lmax to have integer solution k is ηl≤ηm. Similarly, we can prove that the optimal solution k∗ is certainly in closed interval ηl,ηm.We have the following Theorem6 that is similar to Theorem 2. If we prove ξ2∈ηl,ηm, we obtain that ξ2 is the only extreme point of v1(x)·v2(x) in ηl,ηm and it is also the maximum value point of v1(x)·v2(x).Theorem 6.
Under the condition of expression (17), there is an optimal solution k∗ for the problem G2pj,r=P0-ar,dj=dv1v2/Lmax, and the result can be expressed as k∗=ξ2 or ξ2. The optimal solution k∗ is as follows: (I)
Ifξ2∈[ηl,ηm] and ξ2∉[ηl,ηm], then k∗=ξ2;(II)
Ifξ2∈[ηl,ηm] and ξ2∉[ηl,ηm], then k∗=ξ2;(III)
Ifξ2∈[ηl,ηm] and ξ2∈[ηl,ηm],
whenv1ξ2·v2ξ2≤v1ξ2·v2ξ2, then k∗=ξ2;whenv1ξ2·v2ξ2≥v1ξ2·v2ξ2, then k∗=ξ2.


## 4. Conclusions

In this paper, we introduce an aging effect and a learning effect into the cooperative games on scheduling. Two persons have to cooperate in order to process a set of jobs. The objective is to maximize the multiplication of their rational positive cooperative profits. We show that two scheduling problemsG2pj,r=P0+ar,dj=dv1v2/Lmax and G2pj,r=P0-ar,dj=dv1v2/Lmax are polynomially solvable. The sufficient and necessary conditions for the problems to have positive integer solution are proposed.For future research, it is interesting to extend the problems to involve other position-dependent processing times scheduling model. Another interesting future research direction is to analyze the problems with other objective functions such as minimizing the number of late jobs, the total weighted completion time, and tardiness.



---

*Source: 7150637-2017-04-06.xml*