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

Shuang Zhao

doi:10.3934/jimo.2020096

Article Contents

2021, Volume 17, Issue 5: 2817-2835. Doi: 10.3934/jimo.2020096

This issue Previous Article Stability of ground state for the Schrödinger-Poisson equation Next Article A dual-channel supply chain problem with resource-utilization penalty: Who can benefit from sales effort?

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
^*Corresponding author

Received: September 30, 2019

Revised: January 31, 2020

Early access: May 2020

Published: September 2021

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)

Abstract Full Text(HTML) Figure(1) / Table(8) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90B35; Secondary: 90C26.

Citation:

FullText(HTML)

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

Download: Full-size image 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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[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.
[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.
[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.
[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.
[7]	G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1988.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.