# Due-Window Assignment and Resource Allocation Scheduling with Truncated Learning Effect and Position-Dependent Weights

Authors: Shan-Shan Lin
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

This paper studies single-machine due-window assignment scheduling problems with truncated learning effect and resource allocation simultaneously. Linear and convex resource allocation functions under common due-window (CONW) assignment are considered. The goal is to find the optimal due-window starting (finishing) time, resource allocations and job sequence that minimize a weighted sum function of earliness and tardiness, due window starting time, due window size, and total resource consumption cost, where the weight is position-dependent weight. Optimality properties and polynomial time algorithms are proposed to solve these problems.


---

## Body

## 1. Introduction

Scheduling models and problems with learning effects (see Biskup [1]; Lu et al. [2]; Azzouz et al. [3]; Wang et al. [4]) and/or resource allocations (see Shabtay and Steiner [5]; Yang et al. [6]) have become popular topics for scheduling researchers in recent years. Scheduling with learning effects and resource allocations simultaneously was introduced by Wang et al. [7], who focused on single-machine scheduling problems. Lu et al. [8] studied single-machine due-date assignment scheduling with learning effects and resource allocations. They proved that several problems can be solved in polynomial time. Wang and Wang [9] and Li et al. [10] considered common and slack due-window assignment problems with learning effects and resource allocations. Wang and Wang [11] considered single-machine scheduling problems with learning effects and convex resource allocation function. For the scheduling criterion (the total resource compression criterion) minimization subject to the constraint that the total resource compression criterion (the scheduling criterion) is less than or equal to a fixed constant, they proved that the problems can be solved in polynomial time. Wang et al. [12] and Liu and Jiang [13] considered due-date assignment scheduling with job-dependent learning effects and resource allocation. Liu and Jiang [14] considered flow shop due-date assignment scheduling with resource allocation and learning effect. Shi and Wang [15] considered flow shop due-window assignment scheduling with resource allocation and learning effect.In recent years, many researchers focused on the study of scheduling with due-window, where a time interval is assumed, such that jobs completed within this interval are not penalized (Janiak et al. [16] and Wang et al. [17]). Wang et al. [18] considered the single-machine due-window scheduling problems with position-dependent weights. For the weighted sum of earliness and tardiness, due window starting time, and due window size, where the weight only dependent on its position in a sequence (i.e., a position-dependent weight), they proved that the problems can be solved in polynomial time. In this study, we continue the work of Wang et al. [18], i.e., we consider the due-window assignment scheduling problems with learning effect and resource allocation in the single-machine environment. The goal is to find the optimal due-window starting (finishing) time, resource allocations, and job sequence such that a sum of scheduling cost (including weighted sum function of earliness and tardiness, due window starting time, due window size, where the weight is position-dependent weight) and total resource consumption cost is minimized. The contributions of this paper are given as follows. (1) The structural properties of single-machine scheduling problems are derived. (2) For the linear resource allocation, we proved that the sum of scheduling cost and total resource consumption cost can be solved in polynomial time. For the convex resource allocation, three versions of scheduling cost and total resource consumption cost can be solved in polynomial time respectively. (3) It is further extended the model to the case with slack due-window (SLKW) assignment model.The rest of the article is organized as follows: In Section2, we introduce the problem. In Sections 3 and 4, we provide some properties to optimally solve these problems under linear and convex resource allocation. In Section 5, we conclude the paper.


## 2. Problem Formulation

We study a scheduling problem consisting of a set ofn independent jobs N=J1,J2,…,Jn that need to be processed on a single machine. For the linear resource allocation, the actual processing time of job Jj is(1)PjA=p˜jmaxrαj,δ−βjuj,where p˜j is the basic processing time of job Jj (i.e., the processing time without any resource allocation and truncated learning effect), αj≤0 is the job-dependent learning rate (Mosheiov and Sidney [19]) of job Jj, 0<δ<1 is a truncation parameter (Wang et al. [20]), βj is the compression rate of job Jj, and ujis the amount of resource allocated to job Jj and satisfies 0≤uj≤u¯j≤p˜jmaxrαj,δ/βj.For the convex resource allocation, the actual processing time of jobJj is(2)PjA=p˜jmaxrαj,δujη,where η>0 is a constant, i.e., PjA is a convex decreasing function of resource uj.Letd1,d2be the common due-window for all jobs, where d1≥0d2,d1≤d2 denotes the starting (finishing) time of the common due window. The length of the due-window is D=d2−d1. Both d1 and d2are decision variables in this paper. The goal of this paper is to find jointly the optimal due-window location, the optimal resource allocation and sequence π such that the following objective function is minimized:(3)Zd1,d2,π=∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj,where j denotes the job scheduled in jth position, wjj=0,1,2,…,n,n+1 denotes a position- dependent weight, Lj is the earliness-tardiness of job Jj, and(4)Lj=d1−Cj,ford1>Cj,0,ford1≤Cj≤d2,Cj−d2,forCj>d2,where Cj is the completion time of job Jj, j=1,2,…,n. Using the three-field classification, the problem can be denoted as 1CONW,PjA∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj, where PjA∈p˜jmaxrαj,δ−βjuj,p˜jmaxrαj,δ/ujη (Graham et al. [21]), where CONW denotes the common due-window assignment. Wang et al. [18] considered single-machine scheduling problems with CONW and slack due-window (SLKW) assignments problems 1CONW∑j=1nwjLj+w0d1+wn+1D and 1SLKW∑j=1nwjLj+w0q′+wn+1D; for the SLKW model, dj′,dj″ is the due-window of job Jj such that dj′≤dj″, where dj′=PjA+q′,dj″=PjA+q″, j=1,2,…,nlimx⟶∞, q′ and q″ are decision variables and D=q″−q′. Wang et al. [18] proved that these both problems can be solved in Onlogn time, respectively.


## 3. Linear Resource Allocation

Lemma 1 [Wang et al. [18]].
For any given sequenceπ, there exists an optimal sequence in which d1=Ck for some k and d2=Cl for some l,l≥k, where ∑i=0k−1wi≤wn+1≤∑i=0k−1wi, and ∑i=l+1nwi≤wn+1≤∑i=lnwi.Lemma 2.
The objective function of the problem1CONW,PjA∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj can be written as(5)∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj=∑j=1nξjPjA+∑j=1nvjuj,where(6)ξj=∑h=0j−1wh,forj=1,2,…,k;wn+1,forj=k+1,k+2,…,l;∑h=0j−1wh,forj=l+1,l+2,…,n.Proof.
From Lemma1, we have(7)Zd1,d2,π=w0Ck+∑j=1k−1wjCk−Cj+∑j=l+1nwjCj−Cl+wn+1Cl−Ck+∑j=1nvjuj=w0∑j=1kPjA+∑j=1k−1wj∑h=j+1kPhA+∑j=l+1nwj∑h=j+1lPhA+wn+1∑h=k+1lPhA+∑j=1nvjuj=∑j=1kPjA∑h=0j−1wh+∑j=l+1nPjA∑h=jnwh+wn+1∑j=k+1lPjA+∑j=1nvjuj=∑j=1nξjPjA+∑j=1nvjuj,where ξjj=1,2,…,n are given by (6).
From Lemma2, we have(8)Zd1,d2,π=∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj=∑j=1nξjp˜jmaxrαj,δ−βjuj+∑j=1nvjuj=∑j=1nξjp˜jmaxrαj,δ+∑j=1nvj−ξjβjuj.
From (8), for a given sequence, the optimal resource allocation uj∗ with vj−ξjβj<0 should be u¯j; otherwise, uj∗=0, i.e., the optimal resource allocation of job Jj is(9)uj∗=0,if,vj−ξjβj≥0,u¯j,if,vj−ξjβj<0.
For a given sequence, from (8), we can obtain the optimal resource allocation. In order to determine the optimal sequence, let xjr=1 if job Jjj=1,2,…,n is scheduled at position rr=1,2,…,n, and xjr=0, otherwise. Then, the problem 1CONW,PjA=p˜jmaxrαj,δ−βju∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj can be solved by the following assignment problem:(10)Min∑r=1n∑j=1nΨjrxjr,(11)S.T.∑r=1nxjr=1,j=1,2,…,n,(12)∑j=1nxjr=1,r=1,2,…,n,(13)xjr=0or1,j=1,2,…,n,where (14)Ψjr=ξrp˜jmaxrαj,δ,ifvj−ξrβj≥0,j,r=1,2,…,n,ξrp˜jmaxrαj,δ+vj−ξrβju¯j,ifvj−ξrβj<0,j,r=1,2,…,n.
Andξr (r=1,2,…,n) are given by (6).
Based on the above analysis, the problem1CONW,PjA=p˜jmaxrαj,δ−βju∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj can be optimally solved by the following algorithm.Algorithm 1.
Step 1. Calculate the indicesk and l according to Lemma 1.Step 2. Calculate the valuesΨjr by using (14).Step 3. Solve the assignment problem (10)–(13) to determine the optimal job sequence.Step 4. Calculate the optimal resource allocation by (7).Step 5. Calculated1=Ck, d2=Cl.Theorem 1.
The problem1CONW,PjA=p˜jmaxrαj,δ−βju∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj can be solved by Algorithm 1 in On3 time.Proof.
The correctness of Algorithm1 follows from the above analysis. The time complexity of Step 1 is On time, Step 2 is On2 time, Step 3 is On3 time, Step 4 is On, and 5 is On time. Thus, the overall computational complexity of Algorithm 1 is On3.
In order to illustrate Algorithm1 for 1CONW,PjA=p˜jmaxrαj,δ−βju∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj, we present the following example.Example 1.
Data:n=7,δ=0.6, w0=19,w1=20, w2=12,w3=7, w4=14,w5=24, w6=22,w7=15, w8=22, and the other corresponding parameters shown in Table 1.
Solution:Step 1. According to Lemma1, k = 1,l = 6.Step 2. From (5), ξ1=19 , ξ2=ξ3=ξ4=ξ5=ξ6=22,ξ7=15, and the values Ψjr are given in Table 2.Step 3. Stemming from the assignment problem (8)–(11), the optimal job sequence is π=J4,J7,J2,J6,J1,J5,J3.Step 4. From (7), the optimal resource allocation is u4=1, u7=5, u2=3, u6=4, u1=5, u5=2, u3=0.Step 5. Calculated1=C1=C4=7, d2=C6=C5=22.67617, and ∑j=1nwjLj+w0d1+wn+1D+∑j=1nwjLj=886.8757.Table 1
Data for Example1.
JjJ1J2J3J4J5J6J7p˜j2317191018169αj−0.32−0.24−0.33−0.25−0.28−0.3−0.29βj2313421vj31430961520u¯j5361245Table 2
ValuesΨjr for Example 1.
j/r1234567Ψjr=1262.0000200.3414151.0178119.706898.6000098.6000072.000002194.0000160.6827131.3178112.149698.1667987.2849866.851483361.0000332.5343290.8883264.5431250.8000250.8000171.00004142.0000127.9972110.163998.5634990.1228783.5674856.218225202.0000162.1420127.1396104.607788.3385475.7799354.000006212.0000169.9128137.1665116.2334101.195995.2000084.000007171.0000151.9446133.9793122.4548114.1549108.800081.00000Bold numbers are the optimal solution.


## 4. Convex Resource Allocation

### 4.1. Problem1CONW,PjA=p˜jmaxrαj,δ/uj∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj

From Lemma2 and PjA=p˜jmaxrαj,δ/ujη, we have(15)∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj=∑j=1nξjp˜jmaxrαj,δujη+∑j=1nvjuj,where ξj (j=1,2,…,n) are given by (6).By taking the first derivative of the objective given by (15) with respect to uj, equating it to zero and solving it for Jj, we have (16).Lemma 3.
For a given sequence, the optimal resource allocation of the problem1CONW,PjA=p˜jmaxrαj,δ/uj∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj is(16)uj∗=ηξjvj1/η+1×p˜jmaxjαj,δη/η+1.
By substituting (16) into (15), we have(17)∑j=1nξjPjA+∑j=1nvjuj=η−η/η+1+η1/η+1∑j=1nvjp˜jmaxjαj,δη/η+1ξj1/η+1.
Let(18)Ψjr=η−η/η+1+η1/η+1vjp˜jmaxrαj,δη/η+1ξr1/η+1,where ξr (r=1,2,…,n) are given by (6).
As in Section3, for the problem 1CONW,PjA=p˜jmaxrαj,δ/uj∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj, we can propose the following algorithm:Algorithm 2.
Step 1. Calculate the indicesk and l according to Lemma 1.Step 2. Calculate the valuesΨjr by using (18).Step 3. Solve the assignment problem (10)–(13) to determine the optimal job sequence.Step 4. Calculate the optimal resource allocation by (16).Step 5. Calculated1=Ck, d2=Cl.Theorem 2.
Algorithm2 solves the problem 1CONW,PjA=p˜jmaxrαj,δ/uj∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj in On3 time.
In order to illustrate Algorithm2 for 1CONW,PjA=p˜jmaxrαj,δ/uj∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj, we present the following example.Example 2.
Considern=7,δ=0.6, η=2, w0=9,w1=8, w2=12,w3=7, w4=14,w5=24, w6=5,w7=15, w8=22, and the other corresponding parameters shown in Table 3.
Solution:Step 1. According to Lemma1, k = 2,l = 5.Step 2. From (5), ξ1=9, ξ2=17, ξ3=ξ4=ξ5=22, ξ6=20, ξ7=15, and the values Ψjr are given in Table 4.Step 3. Stemming from the assignment problem (8)–(11), the optimal job sequence is π=J2,J1,J3,J7,J6,J5,J4.Step 4. From (14), the optimal resource allocation is u2=10.91533, u1=10.71178, u3=11.53352, u7=5.841858, u6=9.501238, u5=9.251873, u4=5.013141.Step 5. Calculated1=C2=C1=3.370785, d2=C5=C6=6.0368777, and ∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj=440.6014.Table 3
Data for Example2.
JjJ1J2J3J4J5J6J7p˜j1317121018169αj−0.32−0.24−0.33−0.25−0.28−0.3−0.29vj3429658Table 4
ValuesΨjr for Example 2.
j/r1234567Ψjr=145.2090348.2030248.1762245.3084443.3230941.9683438.13077265.4919772.4589574.0017670.6727268.1940164.1622656.87507332.7081734.7135034.6005532.4785431.3437230.3635827.58714478.9484886.9442688.5557984.4099981.3283976.4271667.67740589.1520496.8295397.8277492.7128988.9304083.2668675.19374672.9864278.5425378.9243974.5115371.2592967.7545961.55913768.0357473.5540874.1117570.1022967.1423163.1587857.38356Bold numbers are the optimal solution.


### 4.2. Problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D

In this section, we aim to minimize the following cost function∑j=1nwjLj+w0d1+wn+1D subject to ∑j=1nvjuj≤U¯, 1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D where U¯ is a limitation on the total resource consumption cost. Obviously, in an optimal solution for the problem 1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D the constraint will be satisfied as ∑j=1nvjuj=U¯.Lemma 4.
For a given sequence, the optimal resource allocation of the problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D is(19)uj∗=ξj1/η+1vj−1/η+1p˜jmaxjαj,δη/η+1∑j=1nξj1/η+1p˜jmaxjαj,δη/η+1×U¯,j=1,2,…,n,where ξj (j=1,2,…,n) are given by (6).Proof.
For a given sequenceπ=J1,J2,…,Jn, the Lagrange function is(20)Lu,λ=∑j=1nξjPjA+λ∑j=1nvjuj−U¯=∑j=1nξjp˜jmaxjαj,δujη+λ∑j=1nvjuj−U¯,where λ is the Lagrangian multiplier. Deriving (20) with respect to uj and λ, we have(21)∂Lu,λ∂uj=λvj−ηξj×p˜jmaxjαj,δηujη+1=0.
It follows that(22)uj∗=ηξjp˜jmaxjαj,δη1/η+1λvj1/η+1.
From∑j=1nvjuj=U¯, we have(23)λ1/η+1=∑ηξj1/η+1p˜jvjmaxjαj,δη/η+1U¯.
Finally, inserting (23) into (22), we have (19).
By substituting the valuesuj∗ given in (19) into ∑j=1nξjPjA=∑j=1nξjp˜jmaxjαj,δ/ujη, we have(24)∑j=1nξjPjA=U¯−η∑j=1nvjp˜jmaxjαj,δη/η+1ξj1/η+1η+1.
Similarly to Section4.1, we have the following.Theorem 3.
Problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D can be solved in On3 time.


### 4.3. Problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nwjLj+w0d1+wn+1D≤V¯∑j=1nvjuj

In this section, the inverse version’ of1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D will be considered, i.e., the problem of minimizing ∑j=1nvjuj subject to∑j=1nwjLj+w0d1+wn+1D≤V¯, where V¯ is a given real number.Similarly toSection 4.2, we have.Lemma 5.
For a given sequence, the optimal resource allocation of the problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nwjLj+w0d1+wn+1D≤V¯∑j=1nvjuj is(25)uj∗=V¯−1/ηξj1/η+1vj−1/η+1p˜jmaxjαj,δη/η+1∑j=1nξj1/η+1p˜jvjmaxjαj,δη/η+11/η,where ξjj=1,2,…,n are given by (6).
By substituting the valuesuj∗ given in (25) into ∑j=1nvjuj, we have(26)∑j=1nvjuj=V¯−1/η∑j=1nvjp˜jmaxjαj,δη/η+1ξj1/η+11/η+1.
Similarly toSection 4.2, we have.Theorem 4.
Problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nwjLj+w0d1+wn+1D≤V¯∑j=1nvjuj can be solved in On3 time.Remark.
Obviously, the CONW model can be extended to the slack due-window (SLKW) assignment model. The objective function∑j=1nwjLj+w0d1+wn+1D can be replaced by(27)∑j=1nwjLj+w0q′+wn+1D,where(28)Lj=dj′−Cj,fordj′>Cj,0,ford1≤Cj≤d2,Cj−dj″,forCj>dj″,and D=dj″−dj′=q″−q′.


## 4.1. Problem1CONW,PjA=p˜jmaxrαj,δ/uj∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj

From Lemma2 and PjA=p˜jmaxrαj,δ/ujη, we have(15)∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj=∑j=1nξjp˜jmaxrαj,δujη+∑j=1nvjuj,where ξj (j=1,2,…,n) are given by (6).By taking the first derivative of the objective given by (15) with respect to uj, equating it to zero and solving it for Jj, we have (16).Lemma 3.
For a given sequence, the optimal resource allocation of the problem1CONW,PjA=p˜jmaxrαj,δ/uj∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj is(16)uj∗=ηξjvj1/η+1×p˜jmaxjαj,δη/η+1.
By substituting (16) into (15), we have(17)∑j=1nξjPjA+∑j=1nvjuj=η−η/η+1+η1/η+1∑j=1nvjp˜jmaxjαj,δη/η+1ξj1/η+1.
Let(18)Ψjr=η−η/η+1+η1/η+1vjp˜jmaxrαj,δη/η+1ξr1/η+1,where ξr (r=1,2,…,n) are given by (6).
As in Section3, for the problem 1CONW,PjA=p˜jmaxrαj,δ/uj∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj, we can propose the following algorithm:Algorithm 2.
Step 1. Calculate the indicesk and l according to Lemma 1.Step 2. Calculate the valuesΨjr by using (18).Step 3. Solve the assignment problem (10)–(13) to determine the optimal job sequence.Step 4. Calculate the optimal resource allocation by (16).Step 5. Calculated1=Ck, d2=Cl.Theorem 2.
Algorithm2 solves the problem 1CONW,PjA=p˜jmaxrαj,δ/uj∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj in On3 time.
In order to illustrate Algorithm2 for 1CONW,PjA=p˜jmaxrαj,δ/uj∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj, we present the following example.Example 2.
Considern=7,δ=0.6, η=2, w0=9,w1=8, w2=12,w3=7, w4=14,w5=24, w6=5,w7=15, w8=22, and the other corresponding parameters shown in Table 3.
Solution:Step 1. According to Lemma1, k = 2,l = 5.Step 2. From (5), ξ1=9, ξ2=17, ξ3=ξ4=ξ5=22, ξ6=20, ξ7=15, and the values Ψjr are given in Table 4.Step 3. Stemming from the assignment problem (8)–(11), the optimal job sequence is π=J2,J1,J3,J7,J6,J5,J4.Step 4. From (14), the optimal resource allocation is u2=10.91533, u1=10.71178, u3=11.53352, u7=5.841858, u6=9.501238, u5=9.251873, u4=5.013141.Step 5. Calculated1=C2=C1=3.370785, d2=C5=C6=6.0368777, and ∑j=1nwjLj+w0d1+wn+1D+∑j=1nvjuj=440.6014.Table 3
Data for Example2.
JjJ1J2J3J4J5J6J7p˜j1317121018169αj−0.32−0.24−0.33−0.25−0.28−0.3−0.29vj3429658Table 4
ValuesΨjr for Example 2.
j/r1234567Ψjr=145.2090348.2030248.1762245.3084443.3230941.9683438.13077265.4919772.4589574.0017670.6727268.1940164.1622656.87507332.7081734.7135034.6005532.4785431.3437230.3635827.58714478.9484886.9442688.5557984.4099981.3283976.4271667.67740589.1520496.8295397.8277492.7128988.9304083.2668675.19374672.9864278.5425378.9243974.5115371.2592967.7545961.55913768.0357473.5540874.1117570.1022967.1423163.1587857.38356Bold numbers are the optimal solution.


## 4.2. Problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D

In this section, we aim to minimize the following cost function∑j=1nwjLj+w0d1+wn+1D subject to ∑j=1nvjuj≤U¯, 1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D where U¯ is a limitation on the total resource consumption cost. Obviously, in an optimal solution for the problem 1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D the constraint will be satisfied as ∑j=1nvjuj=U¯.Lemma 4.
For a given sequence, the optimal resource allocation of the problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D is(19)uj∗=ξj1/η+1vj−1/η+1p˜jmaxjαj,δη/η+1∑j=1nξj1/η+1p˜jmaxjαj,δη/η+1×U¯,j=1,2,…,n,where ξj (j=1,2,…,n) are given by (6).Proof.
For a given sequenceπ=J1,J2,…,Jn, the Lagrange function is(20)Lu,λ=∑j=1nξjPjA+λ∑j=1nvjuj−U¯=∑j=1nξjp˜jmaxjαj,δujη+λ∑j=1nvjuj−U¯,where λ is the Lagrangian multiplier. Deriving (20) with respect to uj and λ, we have(21)∂Lu,λ∂uj=λvj−ηξj×p˜jmaxjαj,δηujη+1=0.
It follows that(22)uj∗=ηξjp˜jmaxjαj,δη1/η+1λvj1/η+1.
From∑j=1nvjuj=U¯, we have(23)λ1/η+1=∑ηξj1/η+1p˜jvjmaxjαj,δη/η+1U¯.
Finally, inserting (23) into (22), we have (19).
By substituting the valuesuj∗ given in (19) into ∑j=1nξjPjA=∑j=1nξjp˜jmaxjαj,δ/ujη, we have(24)∑j=1nξjPjA=U¯−η∑j=1nvjp˜jmaxjαj,δη/η+1ξj1/η+1η+1.
Similarly to Section4.1, we have the following.Theorem 3.
Problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D can be solved in On3 time.


## 4.3. Problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nwjLj+w0d1+wn+1D≤V¯∑j=1nvjuj

In this section, the inverse version’ of1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nvjuj≤U¯∑j=1nwjLj+w0d1+wn+1D will be considered, i.e., the problem of minimizing ∑j=1nvjuj subject to∑j=1nwjLj+w0d1+wn+1D≤V¯, where V¯ is a given real number.Similarly toSection 4.2, we have.Lemma 5.
For a given sequence, the optimal resource allocation of the problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nwjLj+w0d1+wn+1D≤V¯∑j=1nvjuj is(25)uj∗=V¯−1/ηξj1/η+1vj−1/η+1p˜jmaxjαj,δη/η+1∑j=1nξj1/η+1p˜jvjmaxjαj,δη/η+11/η,where ξjj=1,2,…,n are given by (6).
By substituting the valuesuj∗ given in (25) into ∑j=1nvjuj, we have(26)∑j=1nvjuj=V¯−1/η∑j=1nvjp˜jmaxjαj,δη/η+1ξj1/η+11/η+1.
Similarly toSection 4.2, we have.Theorem 4.
Problem1CONW,PjA=p˜jmaxrαj,δ/ujη,∑j=1nwjLj+w0d1+wn+1D≤V¯∑j=1nvjuj can be solved in On3 time.Remark.
Obviously, the CONW model can be extended to the slack due-window (SLKW) assignment model. The objective function∑j=1nwjLj+w0d1+wn+1D can be replaced by(27)∑j=1nwjLj+w0q′+wn+1D,where(28)Lj=dj′−Cj,fordj′>Cj,0,ford1≤Cj≤d2,Cj−dj″,forCj>dj″,and D=dj″−dj′=q″−q′.


## 5. Conclusions

This paper considered the single-machine due-window assignment scheduling problems with learning effect and resource allocation. For the linear and convex resource allocations, we showed that some different models are polynomially solvable, respectively. Future research may focus on the flow shop scheduling problems with learning effect and resource allocation or study the Pareto-optimal solutions with respect to the criterion∑j=1nwjLj+w0d1+wn+1D and the resource compression cost ∑j=1nvjuj.



---

*Source: 9260479-2020-10-08.xml*