Research article

Single machine resource allocation scheduling problems with deterioration effect and general positional effect

  • Received: 02 November 2020 Accepted: 08 March 2021 Published: 16 March 2021
  • This paper investigates single machine scheduling problems where the actual processing time of a job is dependent on its starting time, processing position and the amount of resource allocation. We present two unified models and provide a bicriteria analysis for the general scheduling criteria and the total weighted resource consumption. We consider two different versions for treating the two criteria and show that the unified models can be applied to solve scheduling problems under various due window assignment considerations. We prove that two different versions of the problems can be solved in polynomial time, respectively.

    Citation: Chunlai Liu, Chuanhui Xiong. Single machine resource allocation scheduling problems with deterioration effect and general positional effect[J]. Mathematical Biosciences and Engineering, 2021, 18(3): 2562-2578. doi: 10.3934/mbe.2021130

    Related Papers:

    [1] Xuyin Wang, Weiguo Liu, Lu Li, Peizhen Zhao, Ruifeng Zhang . Resource dependent scheduling with truncated learning effects. Mathematical Biosciences and Engineering, 2022, 19(6): 5957-5967. doi: 10.3934/mbe.2022278
    [2] Weiguo Liu, Xuyin Wang, Lu Li, Peizhen Zhao . A maintenance activity scheduling with time-and-position dependent deteriorating effects. Mathematical Biosciences and Engineering, 2022, 19(11): 11756-11767. doi: 10.3934/mbe.2022547
    [3] Dan Yang, Zhiqiang Xie, Chunting Zhang . Multi-flexible integrated scheduling algorithm for multi-flexible integrated scheduling problem with setup times. Mathematical Biosciences and Engineering, 2023, 20(6): 9781-9817. doi: 10.3934/mbe.2023429
    [4] Weiguo Liu, Xuyin Wang, Xiaoxiao Wang, Peizhen Zhao . Due-window assignment scheduling with past-sequence-dependent setup times. Mathematical Biosciences and Engineering, 2022, 19(3): 3110-3126. doi: 10.3934/mbe.2022144
    [5] Yu Shen, Hecheng Li . A new differential evolution using a bilevel optimization model for solving generalized multi-point dynamic aggregation problems. Mathematical Biosciences and Engineering, 2023, 20(8): 13754-13776. doi: 10.3934/mbe.2023612
    [6] Yafei Li, Yuxi Liu . Multi-airport system flight slot optimization method based on absolute fairness. Mathematical Biosciences and Engineering, 2023, 20(10): 17919-17948. doi: 10.3934/mbe.2023797
    [7] Lingling Li, Congbo Li, Li Li, Ying Tang, Qingshan Yang . An integrated approach for remanufacturing job shop scheduling with routing alternatives. Mathematical Biosciences and Engineering, 2019, 16(4): 2063-2085. doi: 10.3934/mbe.2019101
    [8] Zilong Zhuang, Zhiyao Lu, Zizhao Huang, Chengliang Liu, Wei Qin . A novel complex network based dynamic rule selection approach for open shop scheduling problem with release dates. Mathematical Biosciences and Engineering, 2019, 16(5): 4491-4505. doi: 10.3934/mbe.2019224
    [9] Lu-Wen Liao . A branch and bound algorithm for optimal television commercial scheduling. Mathematical Biosciences and Engineering, 2022, 19(5): 4933-4945. doi: 10.3934/mbe.2022231
    [10] Yanpei Liu, Yunjing Zhu, Yanru Bin, Ningning Chen . Resources allocation optimization algorithm based on the comprehensive utility in edge computing applications. Mathematical Biosciences and Engineering, 2022, 19(9): 9147-9167. doi: 10.3934/mbe.2022425
  • This paper investigates single machine scheduling problems where the actual processing time of a job is dependent on its starting time, processing position and the amount of resource allocation. We present two unified models and provide a bicriteria analysis for the general scheduling criteria and the total weighted resource consumption. We consider two different versions for treating the two criteria and show that the unified models can be applied to solve scheduling problems under various due window assignment considerations. We prove that two different versions of the problems can be solved in polynomial time, respectively.



    The resource allocation problem is an important and challenging issue and has attracted a lot of attention with interests for practitioners and researchers [1]. Effective (added) resource allocation can improve the efficiency of operation. However, the usage of the resource, especially abundant usage, will create extra costs and result in pollution. Therefore, how to manage and utilize resources efficiently has become an important issue. Nowadays, low carbon, high efficiency and high customer satisfaction have become crucial factors for companies to gain competitiveness. Manufacturers not only need to maximize profits (i.e., reduce time-dependent measure criterion) but also need to control the extra resource input. Although the stated objectives are often conflicting, a resource allocation scheduling approach that increases revenue and optimizes resources provides an additional chance that can facilitate improvements.

    Scheduling problems with resource allocation mean that the job processing times can be controlled by changing the allocation of resources to jobs. Many researchers have expended vast amounts of effort on this vivid area of scheduling research from JIT [2,40], maintenance activity [3], agent scheduling [4], batch scheduling [5]. A comprehensive discussion on scheduling problems with resource allocation (controllable processing times) is provided by Shabtay et al. [6] and Shioura et al. [7]. In such problem, job scheduling and resource allocation decisions should be coordinated carefully to achieve the most efficient system performance. Therefore, the quality of a solution is measured by two criteria: scheduling criterion and resource consumption cost. Recent studies of resource allocation scheduling problems include Low et al. [8], Shioura et al. [9], Yin et al. [10] and Shabtay et al. [11]. Yin et al. [10] study the single-machine due-window assignment with common flow allowances and resource-dependent processing times. They consider two criteria: one is an integrated cost consisting of job earliness, weighted number of tardy jobs, and due-window assignment cost, and the other is the resource consumption cost. Based on the two criteria, they analyze four different models and provide the algorithm to obtain pareto-optimal schedules. Shabtay et al. [11] study a single-machine scheduling problem with resource allocation and due date assignment. They provide a bicriteria analysis. For the limited total weighted resource consumption, they develop a pseudo-polynomial algorithm and fully polynomial time approximation scheme to minimize the total weighted number of tardy jobs plus due date assignment cost. Recently, Yepes et al. [38] consider the unrelated parallel machine scheduling problem with setup times and additional resources in the setups. Yepes et al. [39] study a bi-objective parallel machine scheduling problem with additional resources during setups. They propose a new multi-objective algorithm.

    In many realistic situations, the processing times of jobs is easily affected by many other factors such as worker's experience or fatigue, task's waiting time, machine abrasion. Related examples can be found in steel production [12], electronics manufacturing [13], pollution containment [14], and so on. In the literature, the studies are commonly known as scheduling with learning effect or deteriorating jobs. For the comprehensive literature reviews on both study categories, the readers may refer to Cheng et al. [15], Biskup [16], Gawiejnowicz [17], and Wang et al. [18]. Sometimes, we cannot obtain the specific function expression of learning/deteriorating effect. Therefore, researchers have recently considered scheduling problems with general learning/deteriorating effect functions. Gordon and Strusevich [19] study two due date assignment and single machine scheduling problems with positionally dependent processing times. They give polynomial-time dynamic programming algorithms for the studied problems. Zhao et al. [20] consider a slack due window assignment and single machine scheduling with position effect and deterioration effect. Yin et al. [21] investigate a due-date assignment and single-machine scheduling with generalized position-dependent deteriorating jobs and deteriorating multi-maintenance activities. Rustogi et al. [22] present polynomial-time algorithms for single machine problems with generalized positional deterioration effects and machine maintenance. Rustogi et al. [23] further study a general model for single machine scheduling problems with time and position dependent effects. They provide solution algorithms for minimizing the makespan and the sum of completion times. Rudek [24] study a parallel machine scheduling problem with varying processing times to minimize the makespan. They present an arbitrary monotonic function dependent on the number of previously processed jobs to describe the actual job processing time.

    In order to be more realistic in modelling a production system, researchers have recently considered scheduling problems with variable processing times and resource allocation simultaneously. Oron [14] describes a real application of scheduling to deal with accidents that involve pollution or contamination. The case is modeled as a single-machine scheduling model with convex resource function and general linear deterioration. They develop a polynomial-time solution for minimizing the makespan. Moreover, they compute the optimal resource allocation policy for a given job instance to minimize the total flowtime. Rudek et al. [25] investigate the scheduling problems with the aging effect and additional resource allocation. They describe an example of a deteriorating system and model it as a single-machine scheduling model. Rudek et al. [26] study the flowshop scheduling problem with the aging effect and additional resource allocation. They provide optimal polynomial time solution algorithms for their special cases of the considered problems. Ji et al. [27] consider slack (SLK) due date assignment and single machine scheduling problem with aging effect, resource allocation and a rate-modifying activity. They provide a polynomial-time algorithm to solve it. Sun et al. [28] study three due date assignment methods for single machine scheduling problems with convex resource allocation and variable job processing times. They show that three versions of the problem can be solved in polynomial time. Lu et al. [29] consider the unrelated parallel-machine resource allocation scheduling problem with deteriorating jobs and learning effect. They prove that the problem is polynomial time solvable for minimizing the weighted sum of the total load, the total completion time, the total absolute deviation of completion time and the total resource cost. Wang et al. [30] consider a single machine scheduling with job-dependent learning effect and convex resource-dependent processing times. They provide the polynomial time algorithms for all studied objective functions. Zhao et al. [31] introduce a unified approach to single-machine scheduling problems with deterioration effect and convex resource allocation subject to an upper bound on the total resource consumption. They show that this unified model can be useful in solving scheduling problems under due date assignment and some scheduling problems that do not involve due dates. Tian et al. [32] study the two-machine no-wait flowshop scheduling with learning effect and resource allocation. They show that some cases including makespan, total completion time and total absolute differences in completion times are all polynomially solvable.

    In the paper, we investigate the resource allocation scheduling model of deterioration effect and general positional effect, which is the general and extensional case of existing research. Moreover, we further study the criterion of minimizing total weighted resource consumption subject to an upper bound on scheduling costs. Two unified models for solving single machine scheduling problems with the deterioration effect, general positional effect and convex resource allocation are presented. And we show that the two unified models can be applied to solve various due window assignment problems. At the same time, our study also indicates that a large set of scheduling problems that have the common feature can be expressed as positional penalties function can be solved by using the unified approach.

    The rest of this paper is organized as follows. The following section gives the problem statements formally. In section 3, two unified models are presented and analyzed. Section 4 is the applications of unified models for solving due-window assignment problems. The last section concludes the paper and suggests topics for future research.

    In this section, we define our problems formally. Consider a production system that consists of n independent jobs, N={J1,J2,,Jn}, that are to be processed without preemption on a single machine at time zero. The machine can process at most one job at a time. In this paper, we propose a more general scheduling model that stems from Rudek et al. [25,26], Sun et al. [28], Wang et al. [30], Zhao et al. [31], and so on. In the model, pj is actual processing times of job Jj which is determined simultaneously by resource allocation, starting time Sj and processing position r. The actual job processing times are given as follows:

    pj=((wjuj)k+bSj)g(r),j=1,2,,n,

    where wj is a positive parameter representing the workload of job Jj, uj is the amount of resource allocated to job Jj, k and b are positive constant, and g(r) is a function that specifies a job-independent positional effect. In earlier papers, the focus has been on particular functions that define the positional factors g(r), e.g., rc (c0 or c0) [13,16] or cr (c0) [16], and so on.

    Let U be the total available amount of resources, R be a certain threshold. A solution for the studied problem is defined by a schedule π and by a resource allocation vector [u1,,un]. The quality of a solution is measured by two different criteria. The first is the scheduling criterion f and the second is the total resource consumption cost which is given by nj=1bjuj. One of our objectives is to determine the optimal job sequence and resource allocation policy to minimize the scheduling criterion f. And another objective is to minimize the total weighted resource consumption cost under a certain threshold R. Therefore, our general problems are given by

    1|pj=((wjuj)k+bSj)g(r),bjujU|f (1)

    and

    1|pj=((wjuj)k+bSj)g(r),fR|bjuj. (2)

    In this section, we present the unified models respectively for solving the problems (1) and (2).

    First, we study problem (1) and consider the following optimization problem (P1).

    minf(x1,x2,...,xn)=a1xk1+a2xk2+...+anxkn
    s.t   b1x1+b2x2+...+bnxnU
    xj>0,j=1,2,,n.

    where aj(j=1,2,...,n),bj(j=1,2,...,n),U and k are positive parameters.

    Lemma 1. For the problem (P1), the optimal values of that minimize the function are xj=U(ajbj)1k+1nj=1(ajbj)1k+1,j=1,2,...,n. The optimal value of f is f=1Uk[nj=1(ajbj)1k+1]k+1.

    Proof. It is obviously that we only need to consider the case b1x1+b2x2+...+bnxn=U.

    Because nj=1bjxj=U, x1=Unj=2bjxjb1. Therefore, we can get

    f(x1,x2,...,xn)=a1bk1(Unj=2bjxj)k+a2xk2++anxkn.

    Note that f is a convex function of xj, and it follows that fxj=0 provide necessary and sufficient conditions for optimality.

    Taking the first derivative of f with respect to xj, we have

    fxj=k[a1b1kbj(Unj=2bjxj)k+1ajxk+1j],j=2,...,n.

    Let fxj=0, then xj=(aja1bjbk1)1k+1(Unj=2bjxj). Therefore,

    nj=2bjxj=nj=2bj(aja1bjbk1)1k+1(Unj=2bjxj).

    This can be further written as nj=2bjxj=Unj=2(ajbkja1bk1)1k+11+nj=2(ajbkja1bk1)1k+1.

    By substituting the above relationship into x1=Unj=2bjxjb1 and solving for x1, we obtain

    x1=U(a1b1)1k+1nj=1(ajbkj)1k+1.

    It follows that xj=U(ajbj)1k+1nj=1(ajbkj)1k+1,j=2,...,n.

    Consequently, we have f=1Uk[nj=1(ajbkj)1k+1]k+1.

    For the problem 1|pj=((wjuj)k+bSj)g(r),bjujU|f, it is obvious that for any given feasible resource allocation, our problem is reduced to determining a job sequence that minimizes the scheduling criterion f. In the following, we show that the same techniques used to solve single-machine scheduling with fixed job processing times pj can be incorporated into the model with the actual job processing times pj=((wjuj)k+bSj)g(r).

    Given the problem 1|pj=((wjuj)k+bSj)g(r),bjujU|f, there is a corresponding problem 1|pj|f with fixed job processing times. For a given schedule π=[J[1],J[2],...,J[n]], we assume that the objective function of the problem 1|pj|f can be expressed as f(π)=nj=1ξjp[j], where ξj are position-dependent parameters. In the following, we will give the expression of the objective function for the problem 1|pj=((wjuj)k+bSj)g(r), bjujU|f. The actual processing times of jobs can be expressed as follows:

    p[1]=(w[1]u[1])kg(1),
    p[2]=(w[2]u[2])kg(2)+α[(w[1]u[1])kg(1)]g(2),
    p[3]=(w[3]u[3])kg(3)+α[(w[2]u[2])kg(2)+(1+αg(2))(w[1]u[1])kg(1)]g(3),
    ,
    p[j]=(w[j]u[j])kg(j)+α[j1l=1g(l)(w[l]u[l])kj1i=l+1(1+αg(i))]g(j),
    ,
    p[n]=(w[n]u[n])kg(n)+α[n1l=1g(l)(w[l]u[l])kn1i=l+1(1+αg(i))]g(n).

    Therefore, for the problem 1|pj=((wjuj)k+bSj)g(r),bjujU|f, we have

    f(π)=nj=1ξjp[j]
    =ξ1(w[1]u[1])kg(1)+ξ2((w[1]u[1])k+b(w[1]u[1])kg(1))g(2)+
    +ξn((w[n]u[n])k+bn1l=1g(l)(w[l]u[l])kn1i=l+1(1+bg(i)))g(n)
    =nj=1φj(w[j]u[j])k. (3)

    where,

    φ1=ξ1g(1)+ξ2bg(2)g(1)++ξnbn1i=2(1+bg(i))g(n)g(1),
    φ2=ξ2g(2)+ξ3bg(3)g(2)++ξnbn1i=3(1+bg(i))g(n)g(2),
    ,
    φj=ξjg(j)+ξj+1bg(j+1)g(j)++ξnbn1i=j+1(1+bg(i))g(n)g(j),
    ,
    φn=ξng(n).

    Note that for a given schedule π=[J[1],J[2],...,J[n]], φj,w[j] (j=1,2,,n) are constants. Let a[j]=φjwk[j] and x[j]=u[j], then f(π)=nj=1a[j]xk[j]. Because the objective function can be written in the format shown in (P1), by Lemma 1, the optimal resource allocation for a given sequence is

    u[j]=U(φjwk[j]b[j])1k+1nj=1(φjw[j]kbk[j])1k+1,j=1,2,...,n.

    Thus, we obtain that the function f(π), under an optimal resource allocation, can be expressed as f(π)=1Uk[nj=1(φjwk[j]bk[j])1k+1]k+1.

    Due to U and k are positive constants, minimizing the function f(π) is equivalent to minimizing the function y=nj=1(φjwk[j]bk[j])1k+1=nj=1φ1k+1jwkk+1[j]bkk+1[j].

    We denote φ1k+1j as ξj and wkk+1[j]bkk+1[j] as p[j], then y is of the form nj=1ξjp[j]. This means that the functions of the problems 1|pj=((wjuj)k+bSj)g(r),bjujU|f and 1|pj|f have the same form.

    Theorem 1. When f is of the form nj=1ξjp[j], the problem 1|pj=((wjuj)k+bSj)g(r), bjujU|f is polynomially solvable if the corresponding problem 1|pj|f is polynomially solvable.

    Proof. Because the objective functions of the problems 1|pj|f and 1|pj=((wjuj)k+bSj)g(r), bjujU|f have the same form, the correctness of the theorem follows.

    In the following, we study problem (2) and consider the following optimization problem (P2).

    minh(x1,x2,...,xn)= b1x1+b2x2+...+bnxn
    s.t.     a1xk1+a2xk2+...+anxknR
    xj>0,j=1,2,,n.

    Lemma 2. For the problem (P2), the optimal values of xj that minimize the function h is xj=R1kb1k+1ja1k+1j(nj=1a1k+1jbkk+1j)1k, j=1,2,,n. The optimal value of h is h=R1k(nj=1a1k+1jbkk+1j)1k+1.

    Proof. It is obvious that we only need to consider the case a1xk1+a2xk2++anxkn=R.

    Because nj=1ajxkj=R and a1xk1=Rnj=2ajxkj. Therefore, we can get

    h(x1,x2,...,xn)=b1(a1Rnj=2ajxkj)1k+b2x2++bnxn.

    Note that h is a convex function of xj, and it follows that hxj=0 provide necessary and sufficient conditions for optimality.

    Taking the first derivative of h with respect to xj, we obtain

    hxj=bjb1aja1k1(Rnj=2ajxkj)1k+1xk+1j,j=2,...,n.

    Let hxj=0, then we have xj=(b1aj)1k+1a1k(k+1)1b1k+1j(Rnj=2ajxkj)1k.

    By substituting (Rnj=2ajxkj)1k=a1k1x1 into xj=(b1aj)1k+1a1k(k+1)1b1k+1j(Rnj=2ajxkj)1k, j=2,...,n, we can get xj=(b1aj)1k+1a1k(k+1)1x1b1k+1ja1k1=(b1aj)1k+1x1b1k+1ja1k+11.

    In order to eliminate the variable x1 in the above equation, we have xkj=(b1aj)kk+1xk1bkk+1jakk+11, ajxkj=a1k+1jbkk+1jakk+11bkk+11xk1, nj=2ajxkj=(a1b1)kk+1xk1nj=2a1k+1jbkk+1j. Based on nj=2ajxkj =Ra1xk1, we can obtain

    R=akk+11a1k+11bkk+11+akk+11nj=2a1k+1jbkk+1jxk1bkk+11=akk+11nj=1a1k+1jbkk+1jxk1bkk+11.

    Therefore, we have

    xk1=akk+11nj=1a1k+1jbkk+1jbkk+11R,x1=a1k+11(nj=1a1k+1jbkk+1j)1kb1k+11R1k.

    It follows that

    xj=R1kb1k+1ja1k+1j(nj=1a1k+1jbkk+1j)1k,j=2,...,n.

    Consequently, we can obtain

    h=nj=1bjxj=R1knj=1a1k+1jbkk+1j(nj=1a1k+1jbkk+1j)1k=R1k(nj=1a1k+1jbkk+1j)1k+1.

    For the problem 1|pj=((wjuj)k+bSj)g(r),fR|bjuj, it is obvious that for any given schedule, our problem is reduced to determining the optimal resource allocation that satisfies the scheduling criterion fR and minimizes the total weighted resource allocation costs. In the following, we will show that the function expressions of the problems 1|pj=((wjuj)k+bSj)g(r),fR|bjuj and 1|pj|f have the same form. Similarly, for a given schedule π=[J[1],J[2],...,J[n]], it is assumed that the objective function of the problem 1|pj|f can be expressed as f(π)=nj=1ξjp[j], where ξj are position-dependent parameters.

    Based on Eq (3), let a[j]=φjwk[j] and x[j]=u[j], then f(π)=nj=1a[j]xk[j]. Therefore, the problem 1|pj=((wjuj)k+bSj)g(r),fR|bjuj can be written in the format shown in (P2). By Lemma 2, the optimal resource allocation for a given sequence is u[j]=R1kb1k+1[j](φjwk[j])1k+1(nj=1(φjwk[j])1k+1bkk+1j)1k. Thus, the objective function can be expressed as bjuj=R1k(nj=1(φjwk[j])1k+1bkk+1[j])1k+1 =R1k(nj=1φ1k+1j(w[j]b[j])kk+1)1k+1.

    Due to R and k are positive constants, minimizing the function bjuj is equivalent to minimizing the function y=nj=1φ1k+1j(w[j]b[j])kk+1. Denote φ1k+1j as ξj and wkk+1[j]bkk+1[j] as p[j], then y=nj=1ξjp[j]. This means that the objective functions of the problems 1|pj=((wjuj)k+bSj)g(r), fR|bjuj and 1|pj|f have the same form.

    Theorem 2. When f is of the form nj=1ξjp[j], the problem 1|pj=((wjuj)k+bSj)g(r), fR|bjuj is polynomially solvable if the corresponding problem 1|pj|f is polynomially solvable.

    Proof. Because the objective functions of the problems 1|pj|f and 1|pj=((wjuj)k+bSj)g(r), fR|bjuj have the same form, the correctness of the theorem follows.

    Due window assignment is the most common and significant problem in modern manufacturing and supply chain management. Integrated due windows assignment and production scheduling has received considerable attention from both practitioners and researchers [33]. There are three main categories of due window assignment models (CON/SLK/DIF due window) in the literature. Common due window (denoted by CON) denotes all jobs have the same due window, that is, a time window [d1,d2]. Slack due window (denoted by SLK) denotes all jobs have the common flow allowances. The due window starting time for the job Jj is defined as d1j=pj+q1. Similarly, the due window completion time for the job Jj is defined as d2j=pj+q2 (q2q1). The window size Dj=d2jd1j is identical for all the jobs. Different due window (denoted by DIF) denotes each job can be assigned a different due window with no restrictions.

    We begin by considering the common due window assignment model. Let D=d2d1 denote the size of the common window. Both d1 and D are decision variables. The objective is to minimize the cost function Z=nj=1(αEj+βTj+γd1+δD), where Ej=max{0,d1Cj} is the earliness for job Jj; Tj=max{0,Cjd2} is the tardiness for job Jj; α,β,γ,δ are the positive weight factor.

    For the fixed job processing times, the following results for CON due window assignment problem are given by Liman et al. [34]. It can be easily showed that the results also hold for our problem.

    Lemma 3. For the problem 1|CON|(αEj+βTj+γd1+δD), there exists an optimal schedule for which both the due window starting time d1 and the due window completion time d2 coincide with the job completion times, i.e., d1=C[l] and d2=C[l+m], respectively, where l=max{n(δγ)α,0} and l+m=max{n(βδ)β,0}.

    Moreover, Z=nj=1(αEj+βTj+γd1+δD)=nj=1ξjp[j], where

    ξj={α(j1)+γn,j=1,,l,δn,j=l+1,,l+m,β(nj+1),j=l+m+1,,n.

    Consequently, the objective function of the problem (PC1) 1|pj=((wjuj)k+bSj)g(r), bjujU,CON|(αEj+βTj+γd1+δD) can be expressed as Z=nj=1φj(w[j]u[j])k, where,

    φ1=ξ1g(1)+ξ2bg(2)g(1)++ξnbn1i=2(1+bg(i))g(n)g(1),
    φ2=ξ2g(2)+ξ3bg(3)g(2)++ξnbn1i=3(1+bg(i))g(n)g(2),
    ,
    φj=ξjg(j)+ξj+1bg(j+1)g(j)++ξnbn1i=j+1(1+bg(i))g(n)g(j),
    ,
    φn=ξng(n).

    Let a[j]=φjwk[j] and x[j]=u[j], then f(π)=nj=1a[j]xk[j]. According to Lemma 1, we can obtain f(π)=1Uk[nj=1(φjwk[j]bk[j])1k+1]k+1.

    Because the problem 1|CON|(αEj+βTj+γd1+δD) can be solved in O(nlogn) time and φ1k+1j are job-independent position weights, from Theorem 1, the problem 1|pj=((wjuj)k+bSj)g(r),bjujU,CON|(αEj+βTj+γd1+δD) can be solved in O(nlogn) time.

    Similarly, according to Theorem 2, the problem (PC2) 1|pj=((wjuj)k+bSj)g(r),CON, (αEj+βTj+γd1+δD)R|bjuj can be solved in O(nlogn) time.

    The formal statement of the solution is provided in the following algorithm.

    Algorithm 1
    Step 1. Calculate the indices l and l+m according to lemma 3.
    Step 2. Calculate the positional weights (φj)1k+1, j=1,,n.
    Step 3. Calculate the job-dependent weights (wjbj)kk+1, j=1,,n.
    Step 4. Obtain the optimal sequence by sequencing the jobs according to the HLP rule. Denote the resulting optimal sequence as π=[J[1],J[2],,J[n]].
    Step 5. Compute the optimal resources allocation u[j]=U(φjwk[j]b[j])1k+1nj=1(φjw[j]kbk[j])1k+1,j=1,2,...,n, and the optimal value of the function f=1Uk[nj=1(φjwk[j]bk[j])1k+1]k+1 for problem PC1; the optimal resources allocation u[j]=(φjwk[j])1k+1(nj=1(φjwk[j])1k+1bkk+1j)1kR1kb1k+1[j], j=1,,n, and the optimal value of the function h=R1k[nj=1φ1k+1j(w[j]b[j])kk+1]1k+1 for problem PC2.

     | Show Table
    DownLoad: CSV

    Theorem 3. The problems PC1 and PC2 can be solved in O(nlogn) time.

    Proof. The correctness of Algorithm 1 follows from the above analysis. Step 1, step 2 and step 3 require O(n) time, step 4 requires O(nlogn) time, and step 5 requires O(n) time. Thus, the overall computational complexity of the algorithm is O(nlogn).

    Example 1. There are n=5 jobs. Let α=10, β=18, γ=2, δ=6, U=50, b=0.1 and k=1. Job parameters are given in Table 1. Without loss of generality, we assume that g(r)=ra and a=0.1. According to Algorithm 1, we first obtain that l=2 and l+m=4. The values of (φj)1k+1 and (wjbj)kk+1 are presented in Table 2. According to the HLP rule, we can get the optimal sequence [J4,J2,J5,J1,J3]. Based on step 5, the optimal resources are u4=3, u2=2.5, u5=11.35, u1=5, u3=1.75. At last, we can figure out that d1=6.45, d2=10.30 and f=362.18 for the problem PC1. Similarly, the problem PC2 can be solved by Algorithm 1.

    Table 1.  The data of Example 1.
    Jobs 1 2 3 4 5
    wj 12 10 14 15 7
    bj 2 4 5 3 1

     | Show Table
    DownLoad: CSV
    Table 2.  The values of positional weights and job-dependent weights.
    j 1 2 3 4 5
    (φj)1k+1 4.45 5.03 5.5 5.23 3.91
    (wjbj)kk+1 4.89 6.32 8.36 6.70 2.64

     | Show Table
    DownLoad: CSV

    Next, we show that slack due window and different due window assignment problems also can be solved by using the unified models. The results of lemma 4 and lemma 5 are proved by Wu et al. [35] and Yue et al. [36] for the fixed job processing times, respectively.

    Lemma 4. For the problem 1|SLK|(αEj+βTj+γd1j+δ(q2q1)), there exists an optimal schedule satisfies the following properties:

    1) prior to a certain position in the sequence, all the jobs are early, and starting from a certain position in the sequence, all the jobs are tardy, i.e., Cjd1j implies Cj1d1j1 and Cjd2j implies Cj+1d2j+1.

    2) the optimal values of q1 and q2 are equal to C[l] and C[m], respectively, where l=max{n(δγ)α,0} and m=max{n(βδ)β,0}.

    Moreover, Z=nj=1(αEj+βTj+γd+δ(q2q1))=nj=1ξjp[j], where

    ξj={αj+γ(n+1),j=1,,l,γ+δn,j=l+1,,m,γ+β(nj),j=m+1,,n.

    Lemma 5. For the problem 1|DIF|(αEj+βTj+γd1j+δDj), there exists an optimal schedule that satisfies the optimal due window starting time d1j and the optimal due window completion time d2j for job Jj is no greater than its completion time Cj, i.e., d1jd2jCj.

    Moreover, Z=nj=1(αEj+βTj+γdj+δDj)=nj=1ξ(nj+1)p[j], where ξ={β,γ,δ}.

    It is also worth noting that Lemma 4 and Lemma 5 also hold for our problems. According to Theorem 1, Theorem 2 and the results above, we can immediately get the following theorem.

    Theorem 4. The problem 1|pj=((wjuj)k+bSj)g(r),bjujU,X| (αEj+βTj+γd1j+δDj) and problem 1|pj=((wjuj)k+bSj)g(r),X, (αEj+βTj+γd1j+δDj)R|bjuj for X{SLK,DIF} can be solved in O(nlogn) time.

    Remark. It is very obvious to see that the unified models can be applied to some scheduling problems, which can be solved by a slightly modified Algorithm 1. Those scheduling problems have the common feature that the scheduling objective function can be expressed as a positional penalties function [37]. For example, the makespan, the sum of completion times, various due dates assignment, and so on.

    In this paper, we study single machine scheduling problems with resource allocation, deterioration and general positional effect. The actual processing time of a job is the function of the amount of resource allocation, starting time and the position. We present two unified models and show that the unified models can be applied to solve various due window assignment problems. Two unified models can describe the general scheduling criterion under the total weighted resource consumption constrain and the total weighted resource allocation costs under the scheduling costs constrain. We show that some scheduling problems can be reduced to the unified models and solved in polynomial time. Identifying the set of Pareto optimal schedules or considering the linear resource consumption functions in the setting is interesting and significant work for future research.

    The authors thank the editor and the reviewers for their useful comments to improve the paper. This work was supported by the National Natural Science Foundation of China under Grant No.71901084, Zhejiang Provincial Natural Science Foundation of China under Grant No. LQ19G020010 and MOE (Ministry of Education of China) Project of Humanities and Social Sciences under Grant No. 19YJC630099.

    All authors declare no conflicts of interest in this paper.



    [1] E. B. Edis, C. Oguz, I. Ozkarahan, Parallel machine scheduling with additional resources: Notation, classification, models and solution methods, Eur. J. Oper. Res., 230 (2013), 449–463.
    [2] Y Leyvand, D Shabtay, G Steiner, L. Yedidsion, Just-in-time scheduling with controllable processing times on parallel machines, J. Comb. Optim., 19 (2010), 347–368. doi: 10.1007/s10878-009-9270-5
    [3] M. Ji, D. Yao, Q. Yang, T. C. E. Cheng, Single-machine common flow allowance scheduling with aging effect, resource allocation, and a rate-modifying activity, Int. Trans. Oper. Res., 22 (2015), 997–1015.
    [4] G. Wan, S. R. Vakati, J. Y. T. Leung, M. Pinedo, Scheduling two agents with controllable processing times, Eur. J. Oper. Res., 205 (2010), 528–539. doi: 10.1016/j.ejor.2010.01.005
    [5] B. Mor, G. Mosheiov, Batch scheduling of identical jobs with controllable processing times, Comput. Oper. Res., 41 (2014), 115–124. doi: 10.1016/j.cor.2013.08.007
    [6] D. Shabtay, G. Steiner, A survey of scheduling with controllable processing times, Discrete Appl. Math., 155 (2007), 1643–1666. doi: 10.1016/j.dam.2007.02.003
    [7] A. Shioura, N. V. Shakhlevich, V. A. Strusevich, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches, Eur. J. Oper. Res., 266 (2018), 795–818. doi: 10.1016/j.ejor.2017.08.034
    [8] C. Low, G. H. Wu, Unrelated parallel-machine scheduling with controllable processing times and eligibility constraints to minimize the makespan, J. Ind. Prod. Eng., 33 (2016), 286–293.
    [9] A. Shioura, N. V. Shakhlevich, V. A. Strusevich, Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times, Math. Program., 153 (2015), 495–534. doi: 10.1007/s10107-014-0814-9
    [10] Y. Yin, D. J. Wang, T. C. E. Cheng, C. C. Wu, Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times, J. Oper. Res. Soc., 67 (2016), 1169–1183. doi: 10.1057/jors.2016.14
    [11] D. Shabtay, G. Steiner, R. Zhang, Optimal coordination of resource allocation, due date assignment and scheduling decisions, Omega, 65 (2016), 41–54.
    [12] L. Tang, H. Gong, J. Liu, F. Li, Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations, Naval Res. Logistics, 61 (2014), 269–285. doi: 10.1002/nav.21582
    [13] D. Biskup, Single-machine scheduling with learning considerations, Eur. J. Oper. Res., 115 (1999), 173–178. doi: 10.1016/S0377-2217(98)00246-X
    [14] D. Oron, Scheduling controllable processing time jobs in a deteriorating environment, J. Oper. Res. Soc., 65 (2014), 49–56. doi: 10.1057/jors.2013.5
    [15] T. C. E. Cheng, Q. Ding, B. M. T. Lin, A concise survey of scheduling with time-dependent processing times, Eur. J. Oper. Res., 152 (2004), 1–13. doi: 10.1016/S0377-2217(02)00909-8
    [16] D. Biskup, A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188 (2008), 315–329. doi: 10.1016/j.ejor.2007.05.040
    [17] S. Gawiejnowicz, Time-Dependent Scheduling, Springer, 2008.
    [18] Y. Wang, X Li, R. Ruiz, An exact algorithm for the shortest path problem with position-based learning effects, IEEE Trans. Sys. Man Cyber. Syst., 47 (2016), 3037–3049.
    [19] V. S. Gordon, V. A. Strusevich, Single machine scheduling and due date assignment with positionally dependent processing times, Eur. J. Oper. Res., 198 (2009), 57–62. doi: 10.1016/j.ejor.2008.07.044
    [20] C. Zhao, H. Tang, Due-window assignment for a single machine scheduling with both deterioration and positional effects, Asia Pac. J. Oper. Res., 32 (2015), 1550014. doi: 10.1142/S0217595915500141
    [21] Y. Yin, W. H. Wu, T. C. E. Cheng, C. C. Wu, Due-date assignment and single-machine scheduling with generalised position-dependent deteriorating jobs and deteriorating multi-maintenance activities, Int. J. Prod. Res., 52 (2014), 2311–2326. doi: 10.1080/00207543.2013.855833
    [22] K. Rustogi, V. A. Strusevich, Single machine scheduling with general positional deterioration and rate-modifying maintenance, Omega, 40 (2012), 791–804. doi: 10.1016/j.omega.2011.12.007
    [23] K. Rustogi, V. A. Strusevich, Combining time and position dependent effects on a single machine subject to rate-modifying activities, Omega, 42 (2014), 166–178. doi: 10.1016/j.omega.2013.05.005
    [24] R. Rudek, Scheduling on parallel processors with varying processing times, Comput. Oper. Res., 81 (2017), 90–101. doi: 10.1016/j.cor.2016.12.007
    [25] A. Rudek, R. Rudek, A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models, Comput. Math. Appl., 62 (2011), 1870–1878. doi: 10.1016/j.camwa.2011.06.030
    [26] A. Rudek, R. Rudek, On flowshop scheduling problems with the aging effect and resource allocation, Int. J. Adv. Manuf. Technol., 62 (2012), 135–145. doi: 10.1007/s00170-011-3809-1
    [27] M. Ji, D. Yao, Q. Yang, T. C. E. Cheng, Single-machine common flow allowance scheduling with aging effect, resource allocation, and a rate-modifying activity, Int. Trans. Oper. Res., 22 (2015), 997–1015.
    [28] L. H. Sun, K. Cui, J. Chen, J. Wang, Due date assignment and convex resource allocation scheduling with variable job processing times, Int. J. Prod. Res., 54 (2016), 3551–3560. doi: 10.1080/00207543.2015.1083628
    [29] Y. Y. Lu, J. Jin, P. Ji, J. B. Wang, Resource-dependent scheduling with deteriorating jobs and learning effects on unrelated parallel machine, Neural Comput. Appl., 27 (2016), 1993–2000. doi: 10.1007/s00521-015-1993-x
    [30] J. B. Wang, J. J. Wang, Research on scheduling with job-dependent learning effect and convex resource-dependent processing times, Int. J. Prod. Res., 53 (2015), 5826–5836. doi: 10.1080/00207543.2015.1010746
    [31] C. Zhao, C. J. Hsu, W. H. Wu, S. R. Cheng, C. C. Wu, Note on a unified approach to the single-machine scheduling problem with a deterioration effect and convex resource allocation, J. Manuf. Syst., 38 (2016), 134–140. doi: 10.1016/j.jmsy.2015.12.002
    [32] Y. Tian, M. Xu, C. Jiang, J. B. Wang, X. Y. Wang, No-wait resource allocation flowshop scheduling with learning effect under limited cost availability, Comput. J., 62 (2019), 90–96. doi: 10.1093/comjnl/bxy034
    [33] G. Mosheiov, A. Sarig, V. Strusevich, Minmax scheduling and due-window assignment with position-dependent processing times and job rejection, 4OR, 2019 (2019), 1–18.
    [34] S. D. Liman, S. S. Panwalkar, S. Thongmee, Common due window size and location determination in a single machine scheduling problem, J. Oper. Res. Soc., 49 (1998), 1007–1010. doi: 10.1057/palgrave.jors.2600601
    [35] Y. B. Wu, L. Wan, X. Y. Wang, Study on due-window assignment scheduling based on common flow allowance, Int. J. Prod. Econ., 165 (2015), 155–157. doi: 10.1016/j.ijpe.2015.04.005
    [36] Q. Yue, G. Wan, Single machine SLK/DIF due window assignment problem with job-dependent linear deterioration effects, J. Oper. Res. Soc., 67 (2016), 872–883. doi: 10.1057/jors.2015.107
    [37] D. Shabtay, N. Gaspar, L. Yedidsion, A bicriteria approach to scheduling a single machine with job rejection and positional penalties, J. Comb. Optim., 23 (2012), 395–424. doi: 10.1007/s10878-010-9350-6
    [38] JC Yepes-Borrero, F Villa, F Perea, J. PabloCaballero-Villalobos, GRASP algorithm for the unrelated parallel machine scheduling problem with setup times and additional resources, Expert Syst. Appl., 141 (2020), 1–12.
    [39] J. C. Yepes-Borrero, F. Perea, R. Ruiz, F. Villa, Bi-objective parallel machine scheduling with additional resources during setups, Eur. J. Oper. Res., Forthcoming, 2020.
    [40] D. Wang, Z. Li, Bicriterion scheduling with a negotiable common due window and resource-dependent processing times, Inf. Sci., 478 (2019), 258–274. doi: 10.1016/j.ins.2018.11.023
  • This article has been cited by:

    1. Xuyin Wang, Weiguo Liu, Lu Li, Peizhen Zhao, Ruifeng Zhang, Resource dependent scheduling with truncated learning effects, 2022, 19, 1551-0018, 5957, 10.3934/mbe.2022278
    2. Jiaxin Wang, Xiwang Guo, Jiacun Wang, Shujin Qin, Liang Qi, Ying Tang, 2022, Discrete Migratory Bird Optimizer for Disassembly Line Balancing Problem Considering Tool Deterioration, 978-1-6654-7243-2, 1, 10.1109/ICNSC55942.2022.10004124
    3. Xuyin Wang, Weiguo Liu, Lu Li, Peizhen Zhao, Ruifeng Zhang, Due date assignment scheduling with positional-dependent weights and proportional setup times, 2022, 19, 1551-0018, 5104, 10.3934/mbe.2022238
    4. Mohammad Reza Komari Alaei, Reza Rostamzadeh, Kadir Albayrak, Zenonas Turskis, Jonas Šaparauskas, Improving prediction accuracy of open shop scheduling problems using hybrid artificial neural network and genetic algorithm, 2024, 25, 1611-1699, 892, 10.3846/jbem.2024.22242
    5. Hongbo Lu, 2024, Research on Elastic Scheduling of Private Cloud Resources in Mobile Social Networks Based on Improved Particle Swarm Optimization, 979-8-3503-8098-9, 925, 10.1109/EEBDA60612.2024.10485921
    6. Shujin Qin, Jiaxin Wang, Jiacun Wang, Xiwang Guo, Liang Qi, Yaping Fu, Linear Disassembly Line Balancing Problem with Tool Deterioration and Solution by Discrete Migratory Bird Optimizer, 2024, 12, 2227-7390, 342, 10.3390/math12020342
  • Reader Comments
  • © 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2641) PDF downloads(105) Cited by(6)

Figures and Tables

Tables(2)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog