American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2020096

Resource allocation flowshop scheduling with learning effect and slack due window assignment

Shuang Zhao ,

Department of Basic, Shenyang Sport University, Shenyang 110102, China

*Corresponding author

Received  October 2019 Revised  February 2020 Published  May 2020

Fund Project: This work was supported by the Liaoning Province Universities and Colleges Basic Scientific Research Project of Youth Project, Education Department of Liaoning (China) (Grant no. LQN2017ST04)

We study flowshop scheduling problems with respect to slack due window assignments, which are operations in which jobs are assigned an individual due window. We combine learning effect and controllable processing times, in which the flowshop has a two-machine no-wait setup. The goal is to determine job sequence, slack due window based on common flow allowance, due window size, and resource allocation. We provide a bicriteria analysis for the scheduling and resource consumption costs. We show that the two costs can be solved in polynomial time utilizing three different combinations.

Keywords: Scheduling, flowshop, learning effect, resource allocation, slack due window assignment.
Mathematics Subject Classification: Primary: 90B35; Secondary: 90C26.
Citation: Shuang Zhao. Resource allocation flowshop scheduling with learning effect and slack due window assignment. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020096
References:
[1]

A. Allahverdi, A survey of scheduling problems with no-wait in process, European J. Oper. Res., 255 (2016), 665-686.  doi: 10.1016/j.ejor.2016.05.036.  Google Scholar

[2]

A. Azzouz, M. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography, Internat. J. Prod. Res., 56 (2018), 1642-1661.  doi: 10.1080/00207543.2017.1355576.  Google Scholar

[3]

D. Biskup, A state-of-the-art review on scheduling with learning effects, European J. Oper. Res., 188 (2008), 315-329.  doi: 10.1016/j.ejor.2007.05.040.  Google Scholar

[4]

F. Gao, M. Liu, J.-J. Wang and Y.-Y. Lu, No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times, Internat. J. Prod. Res., 56 (2018), 2361-2369.  doi: 10.1080/00207543.2017.1371353.  Google Scholar

[5]

X.-N. Geng, J.-B. Wang and D. Bai, Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect, Eng. Optim., 51 (2019), 1301-1323.  doi: 10.1080/0305215X.2018.1521397.  Google Scholar

[6]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.  Google Scholar

[7] G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1988.   Google Scholar
[8]

A. Janiak, W. A. Janiak, T. Krysiak and T. Kwiatkowski, A survey on scheduling problems with due windows, European J. Oper. Res., 242 (2015), 347-357.  doi: 10.1016/j.ejor.2014.09.043.  Google Scholar

[9]

S. Khalilpourazari and M. Mohammadi, A new exact algorithm for solving single machine scheduling problems with learning effects and deteriorating jobs, preprint, arXiv: 1809.03795. Google Scholar

[10]

G. Li, M.-L. Luo, W.-J. Zhang and X.-Y. Wang, Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation, Internat. J. Prod. Res., 53 (2015), 1228-1241.  doi: 10.1080/00207543.2014.954057.  Google Scholar

[11]

X.-X. Liang, M. Liu, Y.-B. Feng, J.-B. Wang and L.-S. Wen, Solution algorithms for single-machine resource allocation scheduling with deteriorating jobs and group technology, Engineering Optimization, (2019). doi: 10.1080/0305215X.2019.1638920.  Google Scholar

[12]

Y. Liu and Z. Feng, Two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times, Comput. Industrial Engineering, 75 (2014), 170-175.  doi: 10.1016/j.cie.2014.06.017.  Google Scholar

[13]

Z. Liu, Z. Wang and Y.-Y. Lu, A bicriteria approach for single machine scheduling with resource allocation, learning effect and a deteriorating maintenance activity, Asia-Pac. J. Oper. Res., 34 (2017), 16pp. doi: 10.1142/S0217595917500117.  Google Scholar

[14]

Y.-Y. Lu, G. Li, Y.-B. Wu and P. Ji, Optimal due-date assignment problem with learning effect and resource-dependent processing times, Optim. Lett., 8 (2014), 113-127.  doi: 10.1007/s11590-012-0467-7.  Google Scholar

[15]

Y.-Y. Lu, J.-B. Wang, P. Ji and H. He, A note on resource allocation scheduling with group technology and learning effects on a single machine, Eng. Optim., 49 (2017), 1621-1632.  doi: 10.1080/0305215X.2016.1265305.  Google Scholar

[16]

M. Mohammadi and S. Khalilpourazari, Minimizing makespan in a single machine scheduling problem with deteriorating jobs and learning effects, Proceedings of the 6th International Conference on Software and Computer Applications, 2017,310-315. doi: 10.1145/3056662.3056715.  Google Scholar

[17]

G. Mosheiov and D. Oron, Job-dependent due-window assignment based on a common flow allowance, Foundations Comput. Decision Sciences, 35 (2010), 185-195.   Google Scholar

[18]

D. Shabtay and 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.  Google Scholar

[19]

H.-B. Shi and J.-B. Wang, Research on common due window assignment flow shop scheduling with learning effect and resource allocation, Eng. Optim., 52 (2020), 669-686.  doi: 10.1080/0305215X.2019.1604698.  Google Scholar

[20]

X. Sun, X. Geng, J.-B. Wang and F. Liu, Convex resource allocation scheduling in the no-wait flowshop with common flow allowance and learning effect, Internat. J. Prod. Res., 57 (2019), 1873-1891.  doi: 10.1080/00207543.2018.1510559.  Google Scholar

[21]

Y. Tian, M. Xu, C. Jiang, J.-B. Wang and 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.  Google Scholar

[22]

J.-B. Wang, X.-N. Geng, L. Liu, J.-J. Wang and Y.-Y. Lu, Single machine CON/SLK due date assignment scheduling with controllable processing time and job-dependent learning effects, Comput. J., 61 (2018), 1329-1337.  doi: 10.1093/comjnl/bxx121.  Google Scholar

[23]

J.-B. Wang, M. Gao, J.-J. Wang, L. Liu and H. He, Scheduling with a position-weighted learning effect and job release dates, Engineering Optimization, (2019). doi: 10.1080/0305215X.2019.1664498.  Google Scholar

[24]

J.-B. Wang and L. Li, Machine scheduling with deteriorating jobs and modifying maintenance activities, Comput. J., 61 (2018), 47-53.  doi: 10.1093/comjnl/bxx032.  Google Scholar

[25]

J.-B. Wang, F. Liu and J.-J. Wang, Research on $m$-machine flow shop scheduling with truncated learning effects, Int. Trans. Oper. Res., 26 (2019), 1135-1151.  doi: 10.1111/itor.12323.  Google Scholar

[26]

J.-B. Wang, and M.-Z. Wang, Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times, Asia-Pac. J. Oper. Res., 31 (2014), 15pp. doi: 10.1142/S0217595914500365.  Google Scholar

[27]

J.-B. Wang and J.-J. Wang, Research on scheduling with job-dependent learning effect and convex resource-dependent processing times, Internat. J. Prod. Res., 53 (2015), 5826-5836.  doi: 10.1080/00207543.2015.1010746.  Google Scholar

[28]

D. Wang, M.-Z. Wang and J.-B. Wang, Single-machine scheduling with learning effect and resource-dependent processing times, Comput. Industrial Engineering, 59 (2010), 458-462.  doi: 10.1016/j.cie.2010.06.002.  Google Scholar

[29]

Y. Yin, T. C. E. Cheng, C.-C. Wu and S.-R. Cheng, Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time, J. Oper. Res. Soc., 65 (2014), 1-13.  doi: 10.1057/jors.2012.161.  Google Scholar

[30]

Y. Yin, D. Wang, T. C. E. Cheng and 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.  Google Scholar

show all references

References:
[1]

A. Allahverdi, A survey of scheduling problems with no-wait in process, European J. Oper. Res., 255 (2016), 665-686.  doi: 10.1016/j.ejor.2016.05.036.  Google Scholar

[2]

A. Azzouz, M. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography, Internat. J. Prod. Res., 56 (2018), 1642-1661.  doi: 10.1080/00207543.2017.1355576.  Google Scholar

[3]

D. Biskup, A state-of-the-art review on scheduling with learning effects, European J. Oper. Res., 188 (2008), 315-329.  doi: 10.1016/j.ejor.2007.05.040.  Google Scholar

[4]

F. Gao, M. Liu, J.-J. Wang and Y.-Y. Lu, No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times, Internat. J. Prod. Res., 56 (2018), 2361-2369.  doi: 10.1080/00207543.2017.1371353.  Google Scholar

[5]

X.-N. Geng, J.-B. Wang and D. Bai, Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect, Eng. Optim., 51 (2019), 1301-1323.  doi: 10.1080/0305215X.2018.1521397.  Google Scholar

[6]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.  Google Scholar

[7] G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1988.   Google Scholar
[8]

A. Janiak, W. A. Janiak, T. Krysiak and T. Kwiatkowski, A survey on scheduling problems with due windows, European J. Oper. Res., 242 (2015), 347-357.  doi: 10.1016/j.ejor.2014.09.043.  Google Scholar

[9]

S. Khalilpourazari and M. Mohammadi, A new exact algorithm for solving single machine scheduling problems with learning effects and deteriorating jobs, preprint, arXiv: 1809.03795. Google Scholar

[10]

G. Li, M.-L. Luo, W.-J. Zhang and X.-Y. Wang, Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation, Internat. J. Prod. Res., 53 (2015), 1228-1241.  doi: 10.1080/00207543.2014.954057.  Google Scholar

[11]

X.-X. Liang, M. Liu, Y.-B. Feng, J.-B. Wang and L.-S. Wen, Solution algorithms for single-machine resource allocation scheduling with deteriorating jobs and group technology, Engineering Optimization, (2019). doi: 10.1080/0305215X.2019.1638920.  Google Scholar

[12]

Y. Liu and Z. Feng, Two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times, Comput. Industrial Engineering, 75 (2014), 170-175.  doi: 10.1016/j.cie.2014.06.017.  Google Scholar

[13]

Z. Liu, Z. Wang and Y.-Y. Lu, A bicriteria approach for single machine scheduling with resource allocation, learning effect and a deteriorating maintenance activity, Asia-Pac. J. Oper. Res., 34 (2017), 16pp. doi: 10.1142/S0217595917500117.  Google Scholar

[14]

Y.-Y. Lu, G. Li, Y.-B. Wu and P. Ji, Optimal due-date assignment problem with learning effect and resource-dependent processing times, Optim. Lett., 8 (2014), 113-127.  doi: 10.1007/s11590-012-0467-7.  Google Scholar

[15]

Y.-Y. Lu, J.-B. Wang, P. Ji and H. He, A note on resource allocation scheduling with group technology and learning effects on a single machine, Eng. Optim., 49 (2017), 1621-1632.  doi: 10.1080/0305215X.2016.1265305.  Google Scholar

[16]

M. Mohammadi and S. Khalilpourazari, Minimizing makespan in a single machine scheduling problem with deteriorating jobs and learning effects, Proceedings of the 6th International Conference on Software and Computer Applications, 2017,310-315. doi: 10.1145/3056662.3056715.  Google Scholar

[17]

G. Mosheiov and D. Oron, Job-dependent due-window assignment based on a common flow allowance, Foundations Comput. Decision Sciences, 35 (2010), 185-195.   Google Scholar

[18]

D. Shabtay and 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.  Google Scholar

[19]

H.-B. Shi and J.-B. Wang, Research on common due window assignment flow shop scheduling with learning effect and resource allocation, Eng. Optim., 52 (2020), 669-686.  doi: 10.1080/0305215X.2019.1604698.  Google Scholar

[20]

X. Sun, X. Geng, J.-B. Wang and F. Liu, Convex resource allocation scheduling in the no-wait flowshop with common flow allowance and learning effect, Internat. J. Prod. Res., 57 (2019), 1873-1891.  doi: 10.1080/00207543.2018.1510559.  Google Scholar

[21]

Y. Tian, M. Xu, C. Jiang, J.-B. Wang and 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.  Google Scholar

[22]

J.-B. Wang, X.-N. Geng, L. Liu, J.-J. Wang and Y.-Y. Lu, Single machine CON/SLK due date assignment scheduling with controllable processing time and job-dependent learning effects, Comput. J., 61 (2018), 1329-1337.  doi: 10.1093/comjnl/bxx121.  Google Scholar

[23]

J.-B. Wang, M. Gao, J.-J. Wang, L. Liu and H. He, Scheduling with a position-weighted learning effect and job release dates, Engineering Optimization, (2019). doi: 10.1080/0305215X.2019.1664498.  Google Scholar

[24]

J.-B. Wang and L. Li, Machine scheduling with deteriorating jobs and modifying maintenance activities, Comput. J., 61 (2018), 47-53.  doi: 10.1093/comjnl/bxx032.  Google Scholar

[25]

J.-B. Wang, F. Liu and J.-J. Wang, Research on $m$-machine flow shop scheduling with truncated learning effects, Int. Trans. Oper. Res., 26 (2019), 1135-1151.  doi: 10.1111/itor.12323.  Google Scholar

[26]

J.-B. Wang, and M.-Z. Wang, Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times, Asia-Pac. J. Oper. Res., 31 (2014), 15pp. doi: 10.1142/S0217595914500365.  Google Scholar

[27]

J.-B. Wang and J.-J. Wang, Research on scheduling with job-dependent learning effect and convex resource-dependent processing times, Internat. J. Prod. Res., 53 (2015), 5826-5836.  doi: 10.1080/00207543.2015.1010746.  Google Scholar

[28]

D. Wang, M.-Z. Wang and J.-B. Wang, Single-machine scheduling with learning effect and resource-dependent processing times, Comput. Industrial Engineering, 59 (2010), 458-462.  doi: 10.1016/j.cie.2010.06.002.  Google Scholar

[29]

Y. Yin, T. C. E. Cheng, C.-C. Wu and S.-R. Cheng, Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time, J. Oper. Res. Soc., 65 (2014), 1-13.  doi: 10.1057/jors.2012.161.  Google Scholar

[30]

Y. Yin, D. Wang, T. C. E. Cheng and 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.  Google Scholar

Figure 1.  A two-machine no-waiting flowshop scheduling
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  List of notations
notations definitions
$ n $ the total number of jobs
$ J_{j} $ $ (j = 1,2,\ldots,n) $ index of job
$ \overline{p}_{j} $ normal processing time of job $ J_{j} $
$ {p}_{j} $ actual processing time of job $ J_{j} $
$ a_{j} $ learning index of job $ J_{j} $
$ b_{j} $ compression rate of job $ J_{j} $
$ u_{j} $ amount of resource that can be allocated to job $ J_{j} $
$ v_{j} $ per time unit cost associated with resource allocated
for job $ J_{j} $
$ \bar{d}_j $ due date for job $ J_j $
$ a $ learning index
$ \eta $ positive constant
$ M_{i} $ $ (i = 1,2) $ index of machine
$ O_{j,i} $ operation of job $ J_j $ processed on machine $ M_i $
$ \overline{p}_{j,i} $ normal processing time of operation $ O_{j,i} $
$ {p}_{j,i} $ actual processing time of operation $ O_{j,i} $
$ a_{j,i} $ learning index of operation $ O_{j,i} $
$ u_{j,i} $ amount of resource that can be allocated to
operation $ O_{j,i} $
$ v_{j,i} $ per time unit cost associated with resource allocated
for operation $ O_{j,i} $
$ C_{j,i} $ completion time of operation $ O_{j,i} $
$ [d_j, d'_j] $ due window of job $ J_j $
$ d_j $ starting time of due window for job $ J_j $
$ d'_j $ finishing time of due window for job $ J_j $
$ D' $ due window size
$ C_j = C_{j,2} $ completion time of job $ J_{j} $
$ W_j $ waiting time of job $ J_{j} $
$ E_j $ earliness of job $ J_{j} $
$ T_j $ tardiness of job $ J_{j} $
$ C_{\max} $ makespan
$ \sum_{j = 1}^n C_j $ total completion time
$ \sum_{j = 1}^n W_j $ waiting completion time
$ \sum_{j = 1}^n\sum_{h = j}^n|C_j-C_h| $ total absolute differences in completion times
$ \sum_{j = 1}^n\sum_{h = j}^n|W_j-W_h| $ total absolute differences in waiting times
Table Options

Download as excel

notations definitions
$ n $ the total number of jobs
$ J_{j} $ $ (j = 1,2,\ldots,n) $ index of job
$ \overline{p}_{j} $ normal processing time of job $ J_{j} $
$ {p}_{j} $ actual processing time of job $ J_{j} $
$ a_{j} $ learning index of job $ J_{j} $
$ b_{j} $ compression rate of job $ J_{j} $
$ u_{j} $ amount of resource that can be allocated to job $ J_{j} $
$ v_{j} $ per time unit cost associated with resource allocated
for job $ J_{j} $
$ \bar{d}_j $ due date for job $ J_j $
$ a $ learning index
$ \eta $ positive constant
$ M_{i} $ $ (i = 1,2) $ index of machine
$ O_{j,i} $ operation of job $ J_j $ processed on machine $ M_i $
$ \overline{p}_{j,i} $ normal processing time of operation $ O_{j,i} $
$ {p}_{j,i} $ actual processing time of operation $ O_{j,i} $
$ a_{j,i} $ learning index of operation $ O_{j,i} $
$ u_{j,i} $ amount of resource that can be allocated to
operation $ O_{j,i} $
$ v_{j,i} $ per time unit cost associated with resource allocated
for operation $ O_{j,i} $
$ C_{j,i} $ completion time of operation $ O_{j,i} $
$ [d_j, d'_j] $ due window of job $ J_j $
$ d_j $ starting time of due window for job $ J_j $
$ d'_j $ finishing time of due window for job $ J_j $
$ D' $ due window size
$ C_j = C_{j,2} $ completion time of job $ J_{j} $
$ W_j $ waiting time of job $ J_{j} $
$ E_j $ earliness of job $ J_{j} $
$ T_j $ tardiness of job $ J_{j} $
$ C_{\max} $ makespan
$ \sum_{j = 1}^n C_j $ total completion time
$ \sum_{j = 1}^n W_j $ waiting completion time
$ \sum_{j = 1}^n\sum_{h = j}^n|C_j-C_h| $ total absolute differences in completion times
$ \sum_{j = 1}^n\sum_{h = j}^n|W_j-W_h| $ total absolute differences in waiting times
Table 2.  Summary of Results, $Z$ is the special condition $v_{j, 1} \overline{p}_{j, 1} = v_{j, 2} \overline{p}_{j, 2} = P'_{j}$
problem complexity reference
$F2\left|NW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}\right|A+ \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Liu and Feng [12]
$F2|NW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X|A$ $O(n^3)$ Tian et al. [21]
$F2\left|NW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, A\leq Y\right|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Tian et al. [21]
$F2|NW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}} \right)^{\eta}, Z, \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X|A$ $O(n \log n)$ Tian et al. [21]
$F2\left|NW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z, A\leq Y\right|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n \log n)$ Tian et al. [21]
$F2\left|NW, CON, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta} \right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Gao et al. [4]
$F2\left|NW, CON, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n\log n)$ Gao et al. [4]
$F2\left|NW, CON, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)$ $O(n^3)$ Geng et al. [5]
$F2|NW, CON, $ $p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, \sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)\leq Y|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Geng et al. [5]
$F2\left|NW, CON, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z, \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)$ $O(n \log n)$ Geng et al. [5]
$F2|NW, CON, $ $p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z, \sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)\leq Y|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n\log n)$ Geng et al. [5]
$F2\left|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma q)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Sun et al. [20]
$F2|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, $ $ \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X|\sum_{j = 1}^n(\alpha E_j+\beta T_j+ q)$ $O(n^3)$ Sun et al. [20]
$F2|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, $ $ \sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma q)\leq Y|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Sun et al. [20]
$F2\left|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma q)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n \log n)$ Sun et al. [20]
$F2|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z, \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X|\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma q)$ $O(n \log n)$ Sun et al. [20]
$F2|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z, \sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma q)\leq Y|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n\log n)$ Sun et al. [20]
$F2\left|NW, CON-DW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a_{j, i}}}{u_{j, i}} \right)^{\eta}\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\delta d +\gamma D)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Shi and Wang [19]
$F2\left|NW, CON-DW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\delta d +\gamma D)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n\log n)$ Shi and Wang [19]
P1, P2, P3 $O(n^3)$ Theorem 1
P1($Z$), P2($Z$), P3($Z$) $O(n\log n)$ Theorem 2
Table Options

Download as excel

problem complexity reference
$F2\left|NW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}\right|A+ \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Liu and Feng [12]
$F2|NW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X|A$ $O(n^3)$ Tian et al. [21]
$F2\left|NW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, A\leq Y\right|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Tian et al. [21]
$F2|NW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}} \right)^{\eta}, Z, \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X|A$ $O(n \log n)$ Tian et al. [21]
$F2\left|NW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z, A\leq Y\right|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n \log n)$ Tian et al. [21]
$F2\left|NW, CON, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta} \right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Gao et al. [4]
$F2\left|NW, CON, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n\log n)$ Gao et al. [4]
$F2\left|NW, CON, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)$ $O(n^3)$ Geng et al. [5]
$F2|NW, CON, $ $p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, \sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)\leq Y|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Geng et al. [5]
$F2\left|NW, CON, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z, \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)$ $O(n \log n)$ Geng et al. [5]
$F2|NW, CON, $ $p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z, \sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma d)\leq Y|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n\log n)$ Geng et al. [5]
$F2\left|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma q)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Sun et al. [20]
$F2|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, $ $ \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X|\sum_{j = 1}^n(\alpha E_j+\beta T_j+ q)$ $O(n^3)$ Sun et al. [20]
$F2|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, $ $ \sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma q)\leq Y|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Sun et al. [20]
$F2\left|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma q)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n \log n)$ Sun et al. [20]
$F2|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z, \sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}\leq X|\sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma q)$ $O(n \log n)$ Sun et al. [20]
$F2|NW, SLK, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z, \sum_{j = 1}^n(\alpha E_j+\beta T_j+\gamma q)\leq Y|\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n\log n)$ Sun et al. [20]
$F2\left|NW, CON-DW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a_{j, i}}}{u_{j, i}} \right)^{\eta}\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\delta d +\gamma D)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n^3)$ Shi and Wang [19]
$F2\left|NW, CON-DW, p_{j, i} = \left(\frac{\overline{p}_{{j, i}}r^{a}}{u_{j, i}}\right)^{\eta}, Z\right|$ $\sum_{j = 1}^n(\alpha E_j+\beta T_j+\delta d +\gamma D)+ \theta\sum_{i = 1}^2\sum_{j = 1}^n v_{j, i}u_{j, i}$ $O(n\log n)$ Shi and Wang [19]
P1, P2, P3 $O(n^3)$ Theorem 1
P1($Z$), P2($Z$), P3($Z$) $O(n\log n)$ Theorem 2
Table 3.  Data for Example 1
$ J_j $ $ J_1 $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $
$ \overline{p}_{j,1} $ 4 6 8 9 10 5 18
$ \overline{p}_{j,2} $ 1 3 5 6 4 17 3
$ v_{j,1} $ 2 5 3 1 6 7 4
$ v_{j,2} $ 3 4 2 4 5 6 8
$ a_{j,1} $ -0.1 -0.2 -0.25 -0.12 -0.3 -0.15 -0.24
$ a_{j,2} $ -0.3 -0.1 -0.35 -0.25 -0.22 -0.13 -0.32
Table Options

Download as excel

$ J_j $ $ J_1 $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $
$ \overline{p}_{j,1} $ 4 6 8 9 10 5 18
$ \overline{p}_{j,2} $ 1 3 5 6 4 17 3
$ v_{j,1} $ 2 5 3 1 6 7 4
$ v_{j,2} $ 3 4 2 4 5 6 8
$ a_{j,1} $ -0.1 -0.2 -0.25 -0.12 -0.3 -0.15 -0.24
$ a_{j,2} $ -0.3 -0.1 -0.35 -0.25 -0.22 -0.13 -0.32
Table 4.  Weights for Example 1
$ r $ 1 2 3 4 5 6 7
$ {W'_r} $ 50 58 63 48 32 16 0
$ {V'_r} $ -2 1 21 22 22 22 6
$ {{\eta '}_r} $ 7.0711 7.4833 8.0000 8.3066 7.3485 6.1644 4.6904
$ {{\vartheta '}_r} $ 7.4833 8.0000 8.3066 7.3485 6.1644 4.6904 2.4495
Table Options

Download as excel

$ r $ 1 2 3 4 5 6 7
$ {W'_r} $ 50 58 63 48 32 16 0
$ {V'_r} $ -2 1 21 22 22 22 6
$ {{\eta '}_r} $ 7.0711 7.4833 8.0000 8.3066 7.3485 6.1644 4.6904
$ {{\vartheta '}_r} $ 7.4833 8.0000 8.3066 7.3485 6.1644 4.6904 2.4495
Table 5.  Values $\lambda_{j, r}$ for Example 1
${j\backslash r}$ 1 2 3 4 5 6 7
$1$ 79.0185 71.0153 66.8296 64.0572 62.0114 60.4040 59.0879
$2$ 320.4994 285.0093 266.2270 253.7116 244.4413 237.1383 231.1477
$3$ 275.0662 226.6246 202.4384 186.8978 175.6899 167.0453 160.0771
$4$ 251.1229 217.0961 199.5329 188.0100 179.5710 172.9821 167.6170
$5$ 564.1964 463.9798 413.9291 381.7710 358.5816 340.6988 326.2867
$6$ 694.1769 631.6463 597.7243 574.7719 557.5800 543.9173 532.6284
$7$ 396.4977 333.0474 300.8013 279.8553 264.6294 252.8128 243.2393
Table Options

Download as excel

${j\backslash r}$ 1 2 3 4 5 6 7
$1$ 79.0185 71.0153 66.8296 64.0572 62.0114 60.4040 59.0879
$2$ 320.4994 285.0093 266.2270 253.7116 244.4413 237.1383 231.1477
$3$ 275.0662 226.6246 202.4384 186.8978 175.6899 167.0453 160.0771
$4$ 251.1229 217.0961 199.5329 188.0100 179.5710 172.9821 167.6170
$5$ 564.1964 463.9798 413.9291 381.7710 358.5816 340.6988 326.2867
$6$ 694.1769 631.6463 597.7243 574.7719 557.5800 543.9173 532.6284
$7$ 396.4977 333.0474 300.8013 279.8553 264.6294 252.8128 243.2393
Table 6.  Data for Example 2
$ J_j $ $ J_1 $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $
$ \overline{p}_{j,1} $ 4 6 5 7 8 7 6
$ \overline{p}_{j,2} $ 2 8 10 14 10 7 5
$ v_{j,1} $ 2 4 4 4 5 5 5
$ v_{j,2} $ 4 3 2 2 4 5 6
$ P_{j} $ 8 24 20 28 40 35 30
Table Options

Download as excel

$ J_j $ $ J_1 $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $
$ \overline{p}_{j,1} $ 4 6 5 7 8 7 6
$ \overline{p}_{j,2} $ 2 8 10 14 10 7 5
$ v_{j,1} $ 2 4 4 4 5 5 5
$ v_{j,2} $ 4 3 2 2 4 5 6
$ P_{j} $ 8 24 20 28 40 35 30
Table 7.  Weights for Example 2
$ r $ 1 2 3 4 5 6 7
$ {W'_r} $ 50 58 63 48 32 16 0
$ {V'_r} $ -2 1 21 22 22 22 6
$ {{\eta '}_r} $ 7.0711 7.4833 8.0000 8.3066 7.3485 6.1644 4.6904
$ {{\vartheta '}_r} $ 7.4833 8.0000 8.3066 7.3485 6.1644 4.6904 2.4495
$ {\Psi'} _r $ 14.5544 13.4790 13.0900 11.8643 9.7939 7.5856 4.8381
Table Options

Download as excel

$ r $ 1 2 3 4 5 6 7
$ {W'_r} $ 50 58 63 48 32 16 0
$ {V'_r} $ -2 1 21 22 22 22 6
$ {{\eta '}_r} $ 7.0711 7.4833 8.0000 8.3066 7.3485 6.1644 4.6904
$ {{\vartheta '}_r} $ 7.4833 8.0000 8.3066 7.3485 6.1644 4.6904 2.4495
$ {\Psi'} _r $ 14.5544 13.4790 13.0900 11.8643 9.7939 7.5856 4.8381
Table 8.  Computation time of Algorithm 1 in ms
jobs ($ n $) Min Mean Max
40 916 992.10 1,060
60 1,368 1,491.60 1,991
80 2,352 2,671.20 2,956
100 3,972 4,232.70 4,618
120 5,182 5,979.85 6,223
140 7,775 7,868.50 8,171
160 8,229 9,142.60 9,915
180 10,892 11,514.70 12,325
200 12,884 13,715.60 14,191
220 14,134 15,125.50 16,119
240 16,185 17,815.60 18,181
260 18,347 19,752.40 20,282
280 20,981 21,156.70 22,941
300 23,823 24,715.90 25,671
Table Options

Download as excel

jobs ($ n $) Min Mean Max
40 916 992.10 1,060
60 1,368 1,491.60 1,991
80 2,352 2,671.20 2,956
100 3,972 4,232.70 4,618
120 5,182 5,979.85 6,223
140 7,775 7,868.50 8,171
160 8,229 9,142.60 9,915
180 10,892 11,514.70 12,325
200 12,884 13,715.60 14,191
220 14,134 15,125.50 16,119
240 16,185 17,815.60 18,181
260 18,347 19,752.40 20,282
280 20,981 21,156.70 22,941
300 23,823 24,715.90 25,671
[1]

Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081
[2]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044
[3]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002
[4]

Kun Hu, Yuanshi Wang. Dynamics of consumer-resource systems with consumer's dispersal between patches. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021077
[5]

Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044
[6]

Ana Rita Nogueira, João Gama, Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021008
[7]

Qing-Qing Yang, Wai-Ki Ching, Wan-Hua He, Na Song. Effect of institutional deleveraging on option valuation problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2097-2118. doi: 10.3934/jimo.2020060
[8]

Meng-Xue Chang, Bang-Sheng Han, Xiao-Ming Fan. Global dynamics of the solution for a bistable reaction diffusion equation with nonlocal effect. Electronic Research Archive, , () : -. doi: 10.3934/era.2021024
[9]

Hao Li, Honglin Chen, Matt Haberland, Andrea L. Bertozzi, P. Jeffrey Brantingham. PDEs on graphs for semi-supervised learning applied to first-person activity recognition in body-worn video. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021039
[10]

Yue Qi, Xiaolin Li, Su Zhang. Optimizing 3-objective portfolio selection with equality constraints and analyzing the effect of varying constraints on the efficient sets. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1531-1556. doi: 10.3934/jimo.2020033
[11]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (37)
  • HTML views (312)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences