#### 期刊菜单

Single Machine Scheduling Problem with Controllable Job Processing Times and Position-Dependent Workloads
DOI: 10.12677/AAM.2019.89180, PDF, HTML, XML, 下载: 765  浏览: 993  国家自然科学基金支持

Abstract: This paper concerns with a single-machine scheduling problem in which each processing time of jobs is controllable by allocating a continuously nonrenewable resource. We assume each pro-cessing time of jobs has a workload that is both job and position-dependent. Two problems are investigated. In the first problem, the total amount of resource for processing times does not exceed an upper bound. The objective is to determine the job sequence and the resource allocation scheme to minimize makespan; while in the second problem, the total amount of resource is not limited, the aim is to determine the amount of resource used, the job sequence and the resource allocation scheme to minimize a total weighted cost of makespan and resource amount. We show that the problems can be solved in polynomial time and present optimal algorithms, respectively.

1. 引言

2. 问题描述

${p}_{jr}\left({u}_{j}\right)={\left({w}_{jr}/{u}_{j}\right)}^{k}\text{\hspace{0.17em}},\text{\hspace{0.17em}}{u}_{j}>0,\text{\hspace{0.17em}}j,\text{\hspace{0.17em}}r=1,2,\cdots ,n$

${Z}_{1}={Z}_{1}\left(\pi ,u\right)={C}_{\mathrm{max}}\left(\pi ,u\right)$

$1|{p}_{jr}\left({u}_{j}\right)={\left({w}_{jr}/{u}_{j}\right)}^{k},{\sum }_{j=1}^{n}{u}_{j}\le U|{Z}_{1}$ (1)

${Z}_{2}={Z}_{2}\left(\pi ,u\right)=\alpha {C}_{\mathrm{max}}\left(\pi ,u\right)+\beta U$

$1|{p}_{jr}\left({u}_{j}\right)={\left(\frac{{w}_{jr}}{{u}_{j}}\right)}^{k}|{Z}_{2}$ (2)

3. 问题(1)的最优解

${Z}_{1}\left(\pi ,u\right)={C}_{\mathrm{max}}\left(\pi ,u\right)={\sum }_{r=1}^{n}{\sum }_{j=1}^{n}{p}_{jr}\left({u}_{j}\right){x}_{jr}={\sum }_{r=1}^{n}{\sum }_{j=1}^{n}{\left({w}_{jr}/{u}_{j}\right)}^{k}{x}_{jr}$ (3)

${u}_{j}^{\ast }=\frac{{\left({\sum }_{r=1}^{n}{w}_{jr}^{k}{x}_{jr}\right)}^{1/\left(k+1\right)}}{{\sum }_{j=1}^{n}{\left({\sum }_{r=1}^{n}{w}_{jr}^{k}{x}_{jr}\right)}^{1/\left(k+1\right)}}U,\text{\hspace{0.17em}}\text{\hspace{0.17em}}j=1,2,\cdots ,n$ (4)

$L\left(u,\lambda \right)={\sum }_{r=1}^{n}{\sum }_{j=1}^{n}{\left({w}_{jr}/{u}_{j}\right)}^{k}{x}_{jr}+\lambda \left\{{\sum }_{j=1}^{n}{u}_{j}-U\right\}$ (5)

$\partial L\left(u,\lambda \right)/\partial \lambda ={\sum }_{j=1}^{n}{u}_{j}-U=0$ (6)

$\partial L\left(u,\lambda \right)/\partial {u}_{j}=\partial {C}_{\mathrm{max}}\left(u,\lambda \right)/\partial {u}_{j}+\lambda =0,\text{\hspace{0.17em}}j=1,2,\cdots ,n$ (7)

$\partial {C}_{\mathrm{max}}\left(u,\lambda \right)/\partial {u}_{j}=\partial {C}_{\mathrm{max}}\left(u,\lambda \right)/\partial {u}_{1},\text{ }j=2,3,\cdots ,n$

${u}_{j}={u}_{1}\frac{{\left({\sum }_{r=1}^{n}{w}_{jr}^{k}{x}_{jr}\right)}^{1/\left(k+1\right)}}{{\left({\sum }_{r=1}^{n}{w}_{1r}^{k}{x}_{1r}\right)}^{1/\left(k+1\right)}},\text{\hspace{0.17em}}j=2,\cdots ,n$ (8)

${u}_{1}=\frac{{\left({\sum }_{r=1}^{n}{w}_{1r}^{k}{x}_{1r}\right)}^{1/\left(k+1\right)}}{{\sum }_{j=1}^{n}{\left({\sum }_{r=1}^{n}{w}_{jr}^{k}{x}_{jr}\right)}^{1/\left(k+1\right)}}U,\text{\hspace{0.17em}}j=2,\cdots ,n$ (9)

${Z}_{1}={U}^{-k}{\left({\sum }_{j=1}^{n}{\left({\sum }_{r=1}^{n}{w}_{jr}^{k}{x}_{jr}\right)}^{1/\left(k+1\right)}\right)}^{k+1}$ (10)

$f={\sum }_{j=1}^{n}{\left({\sum }_{r=1}^{n}{w}_{jr}^{k}{x}_{jr}\right)}^{1/\left(k+1\right)}={\sum }_{j=1}^{n}\left({\sum }_{r=1}^{n}{w}_{jr}^{k/\left(k+1\right)}{x}_{jr}\right)$

$\left\{\begin{array}{l}\text{Min}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\sum }_{j=1}^{n}{\sum }_{r=1}^{n}{w}_{jr}^{k/\left(k+1\right)}{x}_{jr}\text{ }\text{ }\text{\hspace{0.17em}}\text{ }\text{ }\text{ }\text{\hspace{0.17em}}\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{\hspace{0.17em}}\text{ }\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(11\right)\\ \text{s}\text{.t}\text{.}\text{ }\left\{\begin{array}{l}{\sum }_{r=1}^{n}{x}_{jr}=1,\text{\hspace{0.17em}}j=1,\cdots ,n\\ {\sum }_{j=1}^{n}{x}_{jr}=1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}r=1,2,\cdots ,n;\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\left(12\right)\\ {x}_{jr}\in \left\{1,0\right\},\text{\hspace{0.17em}}j,\text{\hspace{0.17em}}r=1,2,\cdots ,n\end{array}\end{array}$

4. 问题(2)的最优解

${Z}_{2}\left(\pi ,u\right)=\alpha {C}_{\mathrm{max}}\left(\pi ,u\right)+\beta U=\alpha {U}^{-k}{B}^{k+1}+\beta U$ (13)

${U}^{*}=B{\left(k\alpha /\beta \right)}^{1/\left(k+1\right)}$ (14)

$\partial {Z}_{2}\left(\pi ,u\right)/\partial U=\beta -k\alpha {B}^{k+1}/{U}^{k+1}=0,\text{\hspace{0.17em}}{\partial }^{2}{Z}_{2}\left(\pi ,u\right)/\partial {U}^{2}=\alpha k\left(k+1\right){B}^{\left(k+1\right)}{U}^{-\left(k+2\right)}>0$

${Z}_{2}^{\ast }=\left[{\left(\beta {\alpha }^{1/k}/k\right)}^{k/\left(k+1\right)}+{\left(k\alpha {\beta }^{k}\right)}^{1/\left(k+1\right)}\right]B=LB$

 [1] Lu, Y.Y, Li, G., Wu, Y.B. and Ji, P. (2014) Optimal Due-Date Assignment Problem with Learning Effect and Re-source-Dependent Processing Times. Optimization Letters, 8,113-127. https://doi.org/10.1007/s11590-012-0467-7 [2] Li, G., Luo, M.L., Zhang, W.J. and Wang, X.Y. (2015) Sin-gle-Machine Due-Window Assignment Scheduling Based on Common Flow Allowance, Learning Effect and Resource Allocation. International Journal of Production Research, 4, 1228-1241. https://doi.org/10.1080/00207543.2014.954057 [3] Wang, J.B. and Wang, M.Z. (2014) Single-Machine Due-Window Assignment and Scheduling with Learning Effect and Resource-Dependent Processing Times. Asia-Pacific Journal of Operational Research, 31, Article ID: 1450036. https://doi.org/10.1142/S0217595914500365 [4] Oron, D. (2014) Scheduling Controllable Processing Time Jobs in a Deteriorating Environment. Journal of the Operational Research Society, 65, 49-56. https://doi.org/10.1057/jors.2013.5 [5] Shabtay, D. and Steiner G. (2007) A Survey of Scheduling with Control-lable Processing Times. Discrete Applied Mathematics, 155, 1643-1666. https://doi.org/10.1016/j.dam.2007.02.003 [6] Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979) Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics, 3, 287-326. https://doi.org/10.1016/S0167-5060(08)70356-X