
This paper studies the Pareto scheduling problem of minimizing total weighted completion time and maximum cost on a single machine. It is known that the problem is strongly NP-hard. Algorithms with running time O(n3) are presented for the following cases: arbitrary processing times, equal release dates and equal weights; equal processing times, arbitrary release dates and equal weights; equal processing times, equal release dates and arbitrary weights.
Citation: Zhimeng Liu, Shuguang Li. Pareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine[J]. Mathematical Biosciences and Engineering, 2022, 19(7): 7337-7348. doi: 10.3934/mbe.2022346
[1] | Pshtiwan Othman Mohammed, Hari Mohan Srivastava, Sarkhel Akbar Mahmood, Kamsing Nonlaopon, Khadijah M. Abualnaja, Y. S. Hamed . Positivity and monotonicity results for discrete fractional operators involving the exponential kernel. Mathematical Biosciences and Engineering, 2022, 19(5): 5120-5133. doi: 10.3934/mbe.2022239 |
[2] | Pshtiwan Othman Mohammed, Christopher S. Goodrich, Aram Bahroz Brzo, Dumitru Baleanu, Yasser S. Hamed . New classifications of monotonicity investigation for discrete operators with Mittag-Leffler kernel. Mathematical Biosciences and Engineering, 2022, 19(4): 4062-4074. doi: 10.3934/mbe.2022186 |
[3] | Maysaa Al Qurashi, Saima Rashid, Sobia Sultana, Hijaz Ahmad, Khaled A. Gepreel . New formulation for discrete dynamical type inequalities via h-discrete fractional operator pertaining to nonsingular kernel. Mathematical Biosciences and Engineering, 2021, 18(2): 1794-1812. doi: 10.3934/mbe.2021093 |
[4] | M. Botros, E. A. A. Ziada, I. L. EL-Kalla . Semi-analytic solutions of nonlinear multidimensional fractional differential equations. Mathematical Biosciences and Engineering, 2022, 19(12): 13306-13320. doi: 10.3934/mbe.2022623 |
[5] | Jian Huang, Zhongdi Cen, Aimin Xu . An efficient numerical method for a time-fractional telegraph equation. Mathematical Biosciences and Engineering, 2022, 19(5): 4672-4689. doi: 10.3934/mbe.2022217 |
[6] | Tahir Khan, Roman Ullah, Gul Zaman, Jehad Alzabut . A mathematical model for the dynamics of SARS-CoV-2 virus using the Caputo-Fabrizio operator. Mathematical Biosciences and Engineering, 2021, 18(5): 6095-6116. doi: 10.3934/mbe.2021305 |
[7] | Ritu Agarwal, Pooja Airan, Mohammad Sajid . Numerical and graphical simulation of the non-linear fractional dynamical system of bone mineralization. Mathematical Biosciences and Engineering, 2024, 21(4): 5138-5163. doi: 10.3934/mbe.2024227 |
[8] | Noura Laksaci, Ahmed Boudaoui, Seham Mahyoub Al-Mekhlafi, Abdon Atangana . Mathematical analysis and numerical simulation for fractal-fractional cancer model. Mathematical Biosciences and Engineering, 2023, 20(10): 18083-18103. doi: 10.3934/mbe.2023803 |
[9] | H. M. Srivastava, Khaled M. Saad, J. F. Gómez-Aguilar, Abdulrhman A. Almadiy . Some new mathematical models of the fractional-order system of human immune against IAV infection. Mathematical Biosciences and Engineering, 2020, 17(5): 4942-4969. doi: 10.3934/mbe.2020268 |
[10] | Debao Yan . Existence results of fractional differential equations with nonlocal double-integral boundary conditions. Mathematical Biosciences and Engineering, 2023, 20(3): 4437-4454. doi: 10.3934/mbe.2023206 |
This paper studies the Pareto scheduling problem of minimizing total weighted completion time and maximum cost on a single machine. It is known that the problem is strongly NP-hard. Algorithms with running time O(n3) are presented for the following cases: arbitrary processing times, equal release dates and equal weights; equal processing times, arbitrary release dates and equal weights; equal processing times, equal release dates and arbitrary weights.
The construction of discrete fractional sums and differences from the knowledge of samples of their corresponding continuous integrals and derivatives arises in the context of discrete fractional calculus; see [1,2,3,4,5,6] for more details. Recently, discrete fractional operators with more general forms of their kernels and properties have gathered attention in both areas of physics and mathematics; see [7,8,9,10].
In discrete fractional calculus theory, we say that F is monotonically increasing at a time step t if the nabla of F is non-negative, i.e., (∇F)(t):=F(t)−F(t−1)≥0 for each t in the time scale set Nc0+1:={c0+1,c0+2,…}. Moreover, the function F is θ−monotonically increasing (or decreasing) on Nc0 if F(t+1)>θF(t)(orF(t+1)<θF(t)) for each t∈Na). In [11,12] the authors considered 1−monotonicity analysis for standard discrete Riemann-Liouville fractional differences defined on N0 and in [13] the authors generalized the above by introducing θ−monotonicity increasing and decreasing functions and then obtained some θ−monotonicity analysis results for discrete Riemann-Liouville fractional differences defined on N0. In [14,15,16], the authors considered monotonicity and positivity analysis for discrete Caputo, Caputo-Fabrizio and Attangana-Baleanu fractional differences and in [17,18] the authors considered monotonicity and positivity results for abstract convolution equations that could be specialized to yield new insights into qualitative properties of fractional difference operators. In [19], the authors presented positivity and monotonicity results for discrete Caputo-Fabrizo fractional operators which cover both the sequential and non-sequential cases, and showed both similarities and dissimilarities between the exponential kernel case (that is included in Caputo-Fabrizo fractional operators) and fractional differences with other types of kernels. Also in [20] the authors extended the results in [19] to discrete Attangana-Baleanu fractional differences with Mittag-Leffler kernels. The main theoretical developments of monotonicity and positivity analysis in discrete fractional calculus can be found in [21,22,23,24] for nabla differences, and in [25,26,27,28] for delta differences.
The main idea in this article is to analyse discrete Caputo-Fabrizo fractional differences with exponential kernels in the Riemann-Liouville sense. The results are based on a notable lemma combined with summation techniques. The purpose of this article is two-fold. First we show the positiveness of discrete fractional operators from a theoretical point of view. Second we shall complement the theoretical results numerically and graphically based on the standard plots and heat map plots.
The plan of the article is as follows. In Section 2 we present discrete fractional operators and the main lemma. Section 3 analyses the discrete fractional operator in a theoretical sense. In Section 4 we discuss our theoretical strategy on standard plots (Subsection 4.1) and heat map plots (Subsection 4.2). Finally, in Section 5 we summarize our findings.
First we recall the definitions in discrete fractional calculus; see [2,3,5] for more information.
Definition 2.1. (see [2,Definition 2.24]). Let c0∈R, 0<θ≤1, F be defined on Nc0 and Λ(θ)>0 be a normalization constant. Then the following operator
(CFRc0∇θF)(t):=Λ(θ)∇tt∑r=c0+1F(r)(1−θ)t−r{t∈Nc0+1}, |
is called the discrete Caputo-Fabrizio fractional operator with exponential kernels in the Riemann-Liouville sense CFR, and the following operator
(CFCc0∇θF)(t):=Λ(θ)t∑r=c0+1(∇rF)(r)(1−θ)t−r{t∈Nc0+1}, |
is called the discrete Caputo-Fabrizo fractional operator with exponential kernels in the Caputo sense CFC.
Definition 2.2 (see [3]). For F:Nc0−κ→R with κ<θ≤κ+1 and κ∈N0, the discrete nabla CFC and CFR fractional differences can be expressed as follows:
(CFCc0∇θF)(t)=(CFCc0∇θ−κ∇κF)(t), |
and
(CFRc0∇θF)(t)=(CFRc0∇θ−κ∇κF)(t), |
respectively, for each t∈Nc0+1.
The following lemma is essential later.
Lemma 2.1. Assume that F is defined on Nc0 and 1<θ<2. Then the CFR fractional difference is
(CFRc0∇θF)(t)=Λ(θ−1){(∇F)(t)+(1−θ)(2−θ)t−c0−2(∇F)(c0+1)+(1−θ)t−1∑r=c0+2(∇rF)(r)(2−θ)t−r−1}, |
for each t∈Nc0+2.
Proof. From Definitions 2.1 and 2.2, the following can be deduced for 1<θ<2:
(CFRc0∇θF)(t)=Λ(θ−1){t∑r=c0+1(∇rF)(r)(2−θ)t−r−t−1∑r=c0+1(∇rF)(r)(2−θ)t−r−1}=Λ(θ−1){(∇F)(t)+t−1∑r=c0+1(∇rF)(r)[(2−θ)t−r−(2−θ)t−r−1]}=Λ(θ−1){(∇F)(t)+(1−θ)(2−θ)t−c0−2(∇F)(c0+1)+(1−θ)t−1∑r=c0+2(∇rF)(r)(2−θ)t−r−1}, |
for each t∈Nc0+2.
In the following theorem, we will show that F is monotonically increasing at two time steps even if (CFRc0∇θF)(t) is negative at the two time steps.
Theorem 3.1. Let the function F be defined on Nc0+1, and let 1<θ<2 and ϵ>0. Assume that
(CFRc0∇θF)(t)>−ϵΛ(θ−1)(∇F)(c0+1)fort∈{c0+2,c0+3}s.t.(∇F)(c0+1)≥0. | (3.1) |
If (1−θ)(2−θ)<−ϵ, then (∇F)(c0+2) and (∇F)(c0+3) are both nonnegative.
Proof. From Lemma 2.1 and condition (3.1) we have
(∇F)(t)≥−(∇F)(c0+1)[(1−θ)(2−θ)t−c0−2+ϵ]−(1−θ)t−1∑r=c0+2(∇rF)(r)(2−θ)t−r−1, | (3.2) |
for each t∈Nc0+2. At t=c0+2, we have
(∇F)(c0+2)≥−(∇F)(c0+1)[(1−θ)+ϵ]−(1−θ)c0+1∑r=c0+2(∇rF)(r)(2−θ)c0+1−r⏟=0≥0, |
where we have used (1−θ)<(1−θ)(2−θ)<−ϵ and (∇F)(c0+1)≥0 by assumption. At t=c0+3, it follows from (3.2) that
(∇F)(c0+3)=−(∇F)(c0+1)[(1−θ)(2−θ)+ϵ]−(1−θ)c0+2∑r=c0+2(∇rF)(r)(2−θ)c0+2−r=−(∇F)(c0+1)⏟≥0[(1−θ)(2−θ)+ϵ]⏟<0−(1−θ)⏟<0(∇F)(c0+2)⏟≥0≥0, | (3.3) |
as required. Hence the proof is completed.
Remark 3.1. It worth mentioning that Figure 1 shows the graph of θ↦(1−θ)(2−θ) for θ∈(1,2).
In order for Theorem 3.1 to be applicable, the allowable range of ϵ is ϵ∈(0,−(2−θ)(1−θ)) for a fixed θ∈(1,2)
Now, we can define the set Hκ,ϵ as follows
Hκ,ϵ:={θ∈(1,2):(1−θ)(2−θ)κ−c0−2<−ϵ}⊆(1,2),∀κ∈Nc0+3. |
The following lemma shows that the collection {Hκ,ϵ}∞κ=c0+1 forms a nested collection of decreasing sets for each ϵ>0.
Lemma 3.1. Let 1<θ<2. Then, for each ϵ>0 and κ∈Nc0+3 we have that Hκ+1,ϵ⊆Hκ,ϵ.
Proof. Let θ∈Hκ+1,ϵ for some fixed but arbitrary κ∈Nc0+3 and ϵ>0. Then we have
(1−θ)(2−θ)κ−c0−1=(1−θ)(2−θ)(2−θ)κ−c0−2<−ϵ. |
Considering 1<θ<2 and κ∈Nc0+3, we have 0<2−θ<1. Consequently, we have
(1−θ)(2−θ)κ−c0−2<−ϵ⋅ 12−θ⏟>1<−ϵ. |
This implies that θ∈Hκ,ϵ, and thus Hκ+1,ϵ⊆Hκ,ϵ.
Now, Theorem 3.1 and Lemma 3.1 lead to the following corollary.
Corollary 3.1. Let F be a function defined on Nc0+1, θ∈(1,2) and
(CFRc0∇θF)(t)>−ϵΛ(θ−1)(∇F)(c0+1)suchthat(∇F)(c0+1)≥0, | (3.4) |
for each t∈Nsc0+3:={c0+3,c0+4,…,s} and some s∈Nc0+3. If θ∈Hs,ϵ, then we have (∇F)(t)≥0 for each t∈Nsc0+1.
Proof. From the assumption θ∈Hs,ϵ and Lemma 3.1, we have
θ∈Hs,ϵ=Hs,ϵ∩s−1⋂κ=c0+3Hκ,ϵ. |
This leads to
(1−θ)(2−θ)t−c0−2<−ϵ, | (3.5) |
for each t∈Nsc0+3.
Now we use the induction process. First for t=c0+3 we obtain (∇F)(c0+3)≥0 directly as in Theorem 3.1 by considering inequalities (Eq 3.4) and (Eq 3.5) together with the given assumption (∇F)(c0+1)≥0. As a result, we can inductively iterate inequality (Eq 3.2) to get
(∇F)(t)≥0, |
for each t∈Nsc0+2. Moreover, (∇F)(c0+1)≥0 by assumption. Thus, (∇F)(t)≥0 for each t∈Nsc0+1 as desired.
In this section, we consider the methodology for the positivity of ∇F based on previous observations in Theorem 3.1 and Corollary 3.1 in such a way that the initial conditions are known. Later, we will illustrate other parts of our article via standard plots and heat maps for different values of θ and ϵ. The computations in this section were performed with MATLAB software.
Example 4.1. Considering Lemma 1 with t:=c0+3:
(CFRc0∇θF)(c0+3)=Λ(θ−1){(∇F)(c0+3)+(1−θ)(2−θ)(∇F)(c0+1)+(1−θ)c0+2∑r=c0+2(∇rF)(r)(2−θ)c0+2−r}. |
For c0=0, it follows that
(CFR0∇θF)(3)=Λ(θ−1){(∇F)(3)+(1−θ)(2−θ)(∇F)(1)+(1−θ)2∑r=2(∇rF)(r)(2−θ)2−r}=Λ(θ−1){(∇F)(3)+(1−θ)(2−θ)(∇F)(1)+(1−θ)(∇F)(2)}=Λ(θ−1){F(3)−F(2)+(1−θ)(2−θ)[F(1)−F(0)]+(1−θ)[F(2)−F(1)]}. |
If we take θ=1.99,F(0)=0,F(1)=1,F(2)=1.001,F(3)=1.005, and ϵ=0.007, we have
(CFR0∇1.99F)(3)=Λ(0.99){0.004+(−0.99)(0.01)(0)+(−0.99)(0.001)}=−0.0069Λ(0.99)>−0.007Λ(0.99)=−ϵΛ(0.99)(∇F)(1). |
In addition, we see that (1−θ)(2−θ)=−0.0099<−0.007=−ϵ. Since the required conditions are satisfied, Theorem 3.1 ensures that (∇F)(3)>0.
In Figure 2, the sets Hκ,0.008 and Hκ,0.004 are shown for different values of κ, respectively in Figure 2a, b. It is noted that Hκ,0.008 and Hκ,0.004 decrease by increasing the values of κ. Moreover, in Figure 2a, the set Hκ,0.008 becomes empty for κ≥45; however, in Figure 2b, we observe the non-emptiness of the set Hκ,0.004 for many larger values of κ up to 90. We think that the measures of Hκ,0.008 and Hκ,0.004 are not symmetrically distributed when κ increases (see Figure 2a, b). We do not have a good conceptual explanation for why this symmetric behavior is observed. In fact, it is not clear why the discrete nabla fractional difference CFRc0∇θ seems to give monotonically when θ→1 rather than for θ→2, specifically, it gives a maximal information when θ is very close to 1 as ϵ→0+.
In the next figure (Figure 3), we have chosen a smaller ϵ (ϵ=0.001), we see that the set Hκ,0.001 is non-empty for κ>320. This tells us that small choices in ϵ give us a more widely applicable result.
In this part, we introduce the set Hκ:={κ:θ∈Hκ,ϵ} to simulate our main theoretical findings for the cardinality of the set Hκ via heat maps in Figure 4a–d. In these figures: we mean the warm colors such as red ones and the cool colors such as blue ones. Moreover, the θ values are on the x−axis and ϵ values are on the y−axis. We choose ϵ in the interval [0.00001, 0.0001]. Then, the conclusion of these figures are as follows:
● In Figure 4a when θ∈(1,2) and Figure 4b when θ∈(1,1.5), we observe that the warmer colors are somewhat skewed toward θ very close to 1, and the cooler colors cover the rest of the figures for θ above 1.05.
● In Figure 4c, d, the warmest colors move strongly towards the lower values of θ, especially, when θ∈(1,1.05). Furthermore, when as θ increases to up to 1.0368, it drops sharply from magenta to cyan, which implies a sharp decrease in the cardinality of Hκ for a small values of ϵ as in the interval [0.00001, 0.0001].
On the other hand, for larger values of ϵ, the set Hκ will tend to be empty even if we select a smaller θ in such an interval (1,1.05). See the following Figure 5a, b for more.
In conclusion, from Figures 4 and 5, we see that: For a smaller value of ϵ, the set Hκ,ϵ tends to remain non-empty (see Figure 4), unlike for a larger value of ϵ (see Figure 5). Furthermore, these verify that Corollary 3.1 will be more applicable for 1<θ<1.05 and 0.01<ϵ<0.1 as shown in Figure 4d.
Although, our numerical data strongly note the sensitivity of the set Hκ when slight increasing in ϵ is observed for θ close to 2 compares with θ close to 1.
In this paper we developed a positivity method for analysing discrete fractional operators of Riemann-Liouville type based on exponential kernels. In our work we have found that (∇F)(3)≥0 when (CFRc0∇θF)(t)>−ϵΛ(θ−1)(∇F)(c0+1) such that (∇F)(c0+1)≥0 and ϵ>0. We continue to extend this result for each value of t in Nsc0+1 as we have done in Corollary 3.1.
In addition we presented standard plots and heat map plots for the discrete problem that is solved numerically. Two of the graphs are standard plots for Hκ,ϵ for different values of κ and ϵ (see Figure 2), and the other six graphs consider the cardinality of Hκ for different values of ϵ and θ (see Figures 4 and 5). These graphs ensure the validity of our theoretical results.
In the future we hope to apply our method to other types of discrete fractional operators which include Mittag-Leffler and their extensions in kernels; see for example [5,6].
This work was supported by the Taif University Researchers Supporting Project Number (TURSP-2020/86), Taif University, Taif, Saudi Arabia.
The authors declare there is no conflict of interest.
[1] |
H. Hoogeveen, Multicriteria scheduling, Eur. J. Oper. Res., 167 (2005), 592–623. https://doi.org/10.1016/j.ejor.2004.07.011 doi: 10.1016/j.ejor.2004.07.011
![]() |
[2] |
D. Jones, S. Firouzy, A. Labib, A. V. Argyriou, Multiple criteria model for allocating new medical robotic devices to treatment centres, Eur. J. Oper. Res., 297 (2022), 652–664. https://doi.org/10.1016/j.ejor.2021.06.003 doi: 10.1016/j.ejor.2021.06.003
![]() |
[3] |
F. F. Ostermeier, On the trade-offs between scheduling objectives for unpaced mixed-model assembly lines, Int. J. Prod. Res., 60 (2022), 866–893. https://doi.org/10.1080/00207543.2020.1845914 doi: 10.1080/00207543.2020.1845914
![]() |
[4] | P. M. Kumar, G. C. Babu, A. Selvaraj, M. Raza, A. K. Luhach, V. G. Daaz, Multi-criteria-based approach for job scheduling in industry 4.0 in smart cities using fuzzy logic, Soft Comput., 25 (2021), 12059–12074. |
[5] | V. T'Kindt, J. C. Billaut, Multicriteria scheduling: theory, models and algorithms, second edition, Springer Verlag, Berlin, 2006. |
[6] | P. Brucker, Scheduling algorithms, fifth edition, Springer, 2007. |
[7] |
G. Steiner, P. Stephenson, Pareto optima for total weighted completion time and maximum lateness on a single machine, Discrete Appl. Math., 155 (2007), 2341–2354. https://doi.org/10.1016/j.dam.2007.06.012 doi: 10.1016/j.dam.2007.06.012
![]() |
[8] |
J. K. Lenstra, A. R. Kan, P. Brucker, Complexity of machine scheduling problems, Ann. Discrete Math., 1 (1977), 343–362. https://doi.org/10.1016/S0167-5060(08)70743-X doi: 10.1016/S0167-5060(08)70743-X
![]() |
[9] |
L. N. V. Wassenhove, F. Gelders, Solving a bicriterion scheduling problem, Eur. J. Oper. Res., 4 (1980), 42–48. https://doi.org/10.1016/0377-2217(80)90038-7 doi: 10.1016/0377-2217(80)90038-7
![]() |
[10] |
T. C. John, Tradeoff solutions in single machine production scheduling for minimizing flow time and maximum penalty, Comput. Oper. Res., 16 (1989), 471–479. https://doi.org/10.1016/0305-0548(89)90034-8 doi: 10.1016/0305-0548(89)90034-8
![]() |
[11] |
J. A. Hoogeveen, S. L. V. D. Velde, Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time, Oper. Res. Lett., 17 (1995), 205–208. https://doi.org/10.1016/0167-6377(95)00023-D doi: 10.1016/0167-6377(95)00023-D
![]() |
[12] |
Y. Gao, J. J. Yuan, A note on Pareto minimizing total completion time and maximum cost, Oper. Res. Lett., 43 (2015), 80–82. https://doi.org/10.1080/01576895.2014.1000811 doi: 10.1080/01576895.2014.1000811
![]() |
[13] |
Y. Gao, J. J. Yuan, Pareto minimizing total completion time and maximum cost with positional due indices, J. Oper. Res. Soc. China, 3 (2015), 381–387. https://doi.org/10.1007/s40305-015-0083-1 doi: 10.1007/s40305-015-0083-1
![]() |
[14] | C. He, H. Lin, X. M. Wang, Single machine bicriteria scheduling with equal-length jobs to minimize total weighted completion time and maximum cost, 4OR-Q. J. Oper. Res., 12 (2014), 87–93. |
[15] |
A. A. Lazarev, D. I. Arkhipov, F. Werner, Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan, Optim. Lett., 11 (2016), 165–177. https://doi.org/10.1007/s11590-016-1003-y doi: 10.1007/s11590-016-1003-y
![]() |
[16] |
J. A. Hoogeveen, Single-machine scheduling to minimize a function of two or three maximum cost criteria, J. Algorithms, 21 (1996), 415–433. https://doi.org/10.1006/jagm.1996.0051 doi: 10.1006/jagm.1996.0051
![]() |
[17] |
S. A. Kravchenko, F. Werner, Parallel machine problems with equal processing times: A survey, J. Scheduling, 14 (2011), 435–444. https://doi.org/10.1007/s10951-011-0231-3 doi: 10.1007/s10951-011-0231-3
![]() |
[18] |
H. Emmons, A note on a scheduling problem with dual criteria, Nav. Res. Log., 22 (1975), 615–616. https://doi.org/10.1002/nav.3800220317 doi: 10.1002/nav.3800220317
![]() |
[19] |
W. E. Smith, Various optimizers for single-stage production, Nav. Res. Log., 3 (1956), 59–66. https://doi.org/10.1002/nav.3800030106 doi: 10.1002/nav.3800030106
![]() |
[20] | T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, third edition, MIT press, 2009. |
[21] | F. Koehler, S. Khuller, Optimal batch schedules for parallel machines, in Proceedings of the 13th International Conference on Algorithms and Data Structures, Springer-VerlagBerlin, Heidelberg, 2013. |