A unified analysis for scheduling problems with variable processing times

Ji-Bo Wang; Bo Zhang; Hongyu He

doi:10.3934/jimo.2021008

Article Contents

2022, Volume 18, Issue 2: 1063-1077. Doi: 10.3934/jimo.2021008

This issue Previous Article Ambulance routing in disaster response considering variable patient condition: NSGA-II and MOPSO algorithms Next Article A control parametrization based path planning method for the quad-rotor uavs

A unified analysis for scheduling problems with variable processing times

1.
School of Science, Shenyang Aerospace University, Shenyang 110136, China
2.
Post-doctoral Mobile Station, Dalian Commodity Exchange, Dalian, China

^*Corresponding author: Ji-Bo Wang
^*Corresponding author: Ji-Bo Wang

Received: May 31, 2020

Revised: September 30, 2020

Early access: January 2021

Published: March 2022

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

This paper considers single-machine scheduling problems with variable processing times, in which the actual processing time of a job is a function of its additional resources, starting time, and position in a sequence. Four problems arising from two criteria (a scheduling cost and a total resource consumption cost) are investigated. Under the linear and convex resource consumption functions, we provide unified approaches and consequently prove that these four problems are solvable in polynomial time.

Keywords:

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

Citation:

Full Text(HTML)

Table 1. List of notations

notations	definitions
$n$	total number of jobs
$J_i$	index of job
$\bar{p}_i$	normal processing time of job $J_i$
$C_i$	completion time of job $J_i$
$W_i$	waiting time of job $J_i$
$p_i$	actual processing time of job $J_i$
$d_i$	due date of job $J_i$
$E_i$	earliness of job $J_i$
$T_i$	tardiness of job $J_i$
$u_i$	amount of resources allocated to job $J_i$
$\bar{u}_i$	the upper bound of $u_i$
$\theta_i$	compression rate corresponding to job $J_i$
$v_i$	the cost allocated to job $J_i$
$\varphi_i$	positional weight of $ith$ position
$[i]$	the job that is placed in $ith$ position
$A$	a truncation parameter
$t$	starting process time of some job
$b$	common deterioration rate
$\sigma$	sequence of all jobs
$C_{\max}$	makespan
$\sum_{i=1}^n C_{i}$	total completion time
$\sum_{i=1}^n W_{i}$	total waiting time
$\sum_{i=1}^n\sum_{j=i}^n\|C_i-C_j\|$	total absolute differences in completion times
$\sum_{i=1}^n\sum_{j=i}^n\|W_i-W_j\|$	total absolute differences in waiting times

| Show Table

DownLoad: CSV

Table 2. Models studied

Ref.	Problem	Relation with this article	Due date methods	Complexity
Wang et al. ^[29]	$1\|p_i=\bar{p}_ir^a+bt-\theta_iu_i\|\delta_1C_{\max}+\delta_2\sum_{i=1}^nC_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i\|C_i-C_j\|+\delta_4\sum_{i=1}^nv_iu_i$ $1\|p_i=\bar{p}_ir^a+bt-\theta_iu_i\|\delta_1C_{\max}+\delta_2\sum_{i=1}^nW_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i\|W_i-W_j\|+\delta_4\sum_{i=1}^nv_iu_i$	$p_i$ is type 1b $g(r)=r^a$, $A=0$ $p_i$ is type 1b $g(r)=r^a$, $A=0$		$O(n^3)$ $O(n^3)$
Li et al. ^[12]	$1\|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a\|\delta_1C_{\max}+\delta_2\sum_{i=1}^nC_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i\|C_i-C_j\|+\delta_4\sum_{i=1}^nv_iu_i$ $1\|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a\|\delta_1C_{\max}+\delta_2\sum_{i=1}^nW_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i\|W_i-W_j\|+\delta_4\sum_{i=1}^nv_iu_i$	$p_i$ is type 2a $g(r)=r^a$, $A=0$ $p_i$ is type 2a $g(r)=r^a$, $A=0$		$O(n\log n)$ $O(n\log n)$
Sun et al. ^[23]	$1\|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a\|\sum_{i=1}^n(\alpha E_i+\beta T_i+\gamma d_i+v_iu_i)$ $1\|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a, \sum_{i=1}^nu_i\leq U\|\sum_{i=1}^n(\alpha E_i+\beta T_i+\gamma d_i)$ $1\|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a, \sum_{i=1}^n(\alpha E_i+\beta T_i+\gamma d_i)\leq V\|\sum_{i=1}^nu_i$	$p_i$ is type 2a $g(r)=r^a, A=0$ $p_i$ is type 2a $g(r)=r^a$, $A=0$ $p_i$ is type 2a $g(r)=r^a$, $A=0$	CON/SLK/DIF CON/SLK/DIF CON/SLK/DIF	$O(nlogn)$ $O(n\log n)$ $O(n\log n)$
Wang et al. ^[27]	$1\|p_i=\bar{p}_i\max\{r^{a_i}, A\}+bt-\theta_iu_i\|\beta_1P+\beta_2\sum_{i=1}^nv_iu_i, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i\|C_i-C_j\|\right\}$ $1\|p_i=\left(\frac{\bar{p}_i\max\{r^{a_i}, A\}}{u_i}\right)^k+bt\|\beta_1P+\beta_2\sum_{i=1}^nv_iu_i, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i\|C_i-C_j\|\right\}$ $1\|p_i=\left(\frac{\bar{p}_i\max\{r^{a_i}, A\}}{u_i}\right)^k+bt, \sum_{i=1}^nu_i\leq U\|P, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i\|C_i-C_j\|\right\}$ $1\|p_i=\left(\frac{\bar{p}_i\max\{r^{a_i}, A\}}{u_i}\right)^k+bt, P\leq V\|\sum_{i=1}^nu_i, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i\|C_i-C_j\|\right\}$	$p_i$ is type 1b $g(r)=r^{a_i}$ $p_i$ is type 2b $g(r)=r^{a_i}$ $p_i$ is type 2b $g(r)=r^{a_i}$ $p_i$ is type 2b $g(r)=r^{a_i}$		$O(n\log n)$ $O(n\log n)$ $O(n\log n)$ $O(n\log n)$
Liu et al. ^[15]	$1\|p_i=(\bar{p}_i-bt)g(r)-\theta_iu_i\|\sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}+\eta\sum v_iu_i$ $1\|\left(\left(\frac{\bar{p}_i}{u_i}\right)^k-bt\right)g(r)\|\sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}+\eta\sum v_iu_i$ $1\|\left(\left(\frac{\bar{p}_i}{u_i}\right)^k-bt\right)g(r), \sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}\leq V\|\sum v_iu_i$ $1\|\left(\left(\frac{\bar{p}_i}{u_i}\right)^k-bt\right)g(r), \sum u_i \leq U\|\sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}$	$p_i$ is type 1a $A=0$ $p_i$ is type 2a $A=0$ $p_i$ is type 2a $A=0$ $p_i$ is type 2a $A=0$	CON/SLK/DIF due window CON/SLK/DIF due window CON/SLK/DIF due window CON/SLK/DIF due window	$O(n^3)$ $O(n\log n)$ $O(n\log n)$ h$O(n\log n)$
This paper	P1: $1\|p_i\in\{\mbox {type 1a, type 1b}\}\|\sum_{i=1}^np_{[i]}\varphi_i+\eta\sum_{i=1}^nv_iu_i$ P1: $1\|p_i\in\{\mbox{type 1a, type 1b}\}\|P+\eta\sum_{i=1}^nv_iu_i$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i\|C_i-C_j\|, \sum_{i=1}^n\sum_{j=1}^i\|W_i-W_j\|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ P2: $1\|p_i\in\{\mbox {type 2a, type 2b}\}\|P+\eta\sum_{i=1}^nv_iu_i$hP2: $1\|p_i\in\{\mbox {type 2a, type 2b}\}\|\sum_{i=1}^np_{[i]}\varphi_i+\eta\sum_{i=1}^nv_iu_i$ P2: $1\|p_i\in\{\mbox {type 2a, type 2b}\}\|P+\eta\sum_{i=1}^nv_iu_i$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i\|C_i-C_j\|, \sum_{i=1}^n\sum_{j=1}^i\|W_i-W_j\|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ P3: $1\|p_i\in\{\mbox{type 2a, type 2b}\}, \sum_{i=1}^np_{[i]}\varphi_i\leq \bar{Z}\|\sum_{i=1}^nv_iu_i$ P3: $1\|p_i\in\{\mbox{type 2a, type 2b}\}, P\leq \bar{Z}\|\sum_{i=1}^nv_iu_i$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i\|C_i-C_j\|, \sum_{i=1}^n\sum_{j=1}^i\|W_i-W_j\|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ P4: $1\|p_i\in\{\mbox{type 2a, type 2b}\}, \sum_{i=1}^nv_iu_i\leq\bar{V}\|\sum_{i=1}^np_{[i]}\psi_i$ P4: $1\|p_i\in\{\mbox{type 2a, type 2b}\}, \sum_{i=1}^nv_iu_i\leq\bar{V}\|P$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i\|C_i-C_j\|, \sum_{i=1}^n\sum_{j=1}^i\|W_i-W_j\|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$	$p_i$ is type 1a/1b $p_i$ is type 1a/1b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b		$O(n^3)$ $O(n^3)$ $O(n\log n)$ $o(n\log n)$ $O(n\log n)$ $o(n\log n)$ $O(n\log n)$ $o(n\log n)$
$W_i$, $T_i, E_i$ is the waiting time, earliness, tardiness of job $J_i$, respectively; $C_{max}$ is the makespan of all jobs; $\delta_1, \delta_2, \delta_3, \delta_4, \alpha, \beta, \gamma, \delta, \sigma, \beta_1, \beta_2, U$ and $V$ are given constants

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	G. I. Adamopoulos and C. P. Pappis, Single machine scheduling with flow allowances, Journal of the Operational Research Society, 47 (1996), 1280-1285.
[2]	A. Agnetis, J. C. Billaut, S. Gawiejnowicz, D. Pacciarelli and A. Soukhal, Multiagent Scheduling: Models and Algorithms, Springer, Heidelberg, 2014. doi: 10.1007/978-3-642-41880-8.
[3]	A. Azzouz, M. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography, International Journal of Production Research, 56 (2017), 1-20.
[4]	A. Bachman and A. Janiak, Scheduling deteriorating jobs dependent on resources for the makespan minimization, Operations Research Proceedings, 2000 (Dresden), Springer, Berlin, 2001, 29–34.
[5]	D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008), 315-329. doi: 10.1016/j.ejor.2007.05.040.
[6]	J. Blazewicz, K. H. Ecker, E. Pesch, G. Schmidt, M. Sterna and J. Weglarz, Handbook on Scheduling, Springer, Berlin, 2019.
[7]	S. Gawiejnowicz, A note on scheduling on a single processor with speed dependent on a number of executed jobs, Information Processing Letters, 57 (1996), 297-300. doi: 10.1016/0020-0190(96)00021-X.
[8]	S. Gawiejnowicz, Time-Dependent Scheduling, Springer-Verlag, Berlin, 2008,377 pp.
[9]	S. Gawiejnowicz, A review of four decades of time-dependent scheduling: Main results, new topics, and open problems, Journal of Scheduling, 23 (2020), 3-47. doi: 10.1007/s10951-019-00630-w.
[10]	G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, 2nd ed., Cambridge University Press, Cambridge, 1988,324 pp.
[11]	Y. Leyvand, D. Shabtay and G. Steiner, A unified approach for scheduling with convex resource consumption functions using positional penalties, European Journal of Operational Research, 206 (2010), 301-312. doi: 10.1016/j.ejor.2010.02.026.
[12]	X.-J. Li, J.-J. Wang and X.-R. Wang, Single-machine scheduling with learning effect, deteriorating jobs and convex resource dependent processing times, Asia-Pacific Journal of Operational Research, 32 (2015), 1550033, 12 pp. doi: 10.1142/S0217595915500335.
[13]	S. D. Liman, S. S. Panwalkar and S. Thongmee, Determination of common due window location in a single machine scheduling problem, European Journal of Operational Research, 93 (1996), 68-74.
[14]	S. D. Liman, S. S. Panwalkar and S. Thongmee, Common due window size and location determination in a single machine scheduling problem, Journal of the Operational Research Society, 49 (1998), 1007-1010.
[15]	L. Liu, J.-J. Wang, F. Liu and M. Liu, Single machine due window assignment and resource allocation scheduling problems with learning and general positional effects, Journal of Manufacturing Systems, 43 (2017), 1-14.
[16]	G. Mosheiov and D. Oron, Job-dependent due-window assignment based on a common flow allowance, Foundations of Computing and Decision Sciences, 35 (2010), 185-195.
[17]	D. Oron, Scheduling controllable processing time jobs in a deteriorating environment, Journal of the Operational Research Society, 65 (2014), 49-56.
[18]	S. S. Panwalkar, M. L. Smith and A. Seidmann, Common due-date assignment to minimize total penalty for the one machine scheduling problem, Operations Research, 30 (1982), 391-399.
[19]	K. Rustogi and V. A. Strusevich, Simple matching vs linear assignment in scheduling models with positional effects: A critical review, European Journal of Operational Research, 222 (2012), 393-407. doi: 10.1016/j.ejor.2012.04.037.
[20]	A. Seidmann, S. S. Panwalkar and M. L. Smith, Optimal assignment of due dates for a single processor scheduling problem, International Journal of Production Research, 19 (1981), 393-399.
[21]	D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 155 (2007), 1643-1666. doi: 10.1016/j.dam.2007.02.003.
[22]	V. A. Strusevich and K. Rustogi, Scheduling with times-changing effects and rate-modifying activities, Springer, Berlin, 2017.
[23]	L.-H. Sun, K. Cui, J.-H. Chen and J. Wang, Due-date assignment and convex resource allocation scheduling with variable job processing times, International Journal of Production Research, 54 (2016), 3551-3560.
[24]	X.-R. Wang, J. Jin, J.-B. Wang and P. Ji, Single machine scheduling with truncated job-dependent learning effect, Optimization Letters, 8 (2014), 669-677. doi: 10.1007/s11590-012-0579-0.
[25]	J.-B. Wang and X.-X. Liang, Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint, Engineering Optimization, 51 (2019), 231-246. doi: 10.1080/0305215X.2018.1454442.
[26]	J.-B. Wang, L. Liu and C. Wang, Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs, Applied Mathematical Modelling, 37 (2013), 8394-8400. doi: 10.1016/j.apm.2013.03.041.
[27]	J.-B. Wang, M. Liu, N. Yin and P. Ji, Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects, Journal of Industrial and Management Optimization, 13 (2017), 1025-1039. doi: 10.3934/jimo.2016060.
[28]	J.-B. Wang and M.-Z. Wang, Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time, Computer and Operations Research, 39 (2012), 492-497. doi: 10.1016/j.cor.2011.05.026.
[29]	J.-B. Wang, M.-Z. Wang and P. Ji, Scheduling jobs with processing times dependent on position, starting time and allotted resource, Asia-Pacific Journal of Operational Research, 29 (2012), 1250030, 15 pp. doi: 10.1142/S0217595912500303.
[30]	J.-B. Wang, X.-Y. Wang, L.-H. Sun and L.-Y. Sun, Scheduling jobs with truncated exponential learning functions, Optimization Letters, 7 (2013), 1857-1873. doi: 10.1007/s11590-011-0433-9.
[31]	T. P. Wright, Factors affecting the cost of airplanes, Journal of the Aeronautical Sciences, 3 (1936), 122-128.
[32]	Y.-B. Wu, L. Wan and X.-Y. Wang, Study on due-window assignment scheduling based on common flow allowance, International Journal of Production Economics, 165 (2015), 155-157.
[33]	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, Journal of the Operational Research Society, 65 (2013), 1-13.
[34]	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 allocation, Journal of the Operational Research Society, 67 (2016), 1169-1183.
[35]	Y. Yin, D. Wang, T. C. E. Cheng and C.-C. Wu, CON/SLK due date assignment and scheduling on a single machine with two agents, Naval Research Logistics, 63 (2016), 416-429. doi: 10.1002/nav.21700.