no. 4-5
Single-machine past-sequence-dependent setup times scheduling with resource allocation and learning effect
Zhu, Zhanguo1, 2  ; Chu, Feng2  ; Yu, Yugang3  ; Sun, Linyan4 
1 College of Economics and Management, Nanjing Agricultural University, Nanjing 210095, P.R. China
2 Laboratoire d’informatique, biologie intégrative et systèmes complexes (IBISC), EA 4526, Université d’Evry Val d’Essonne, 91020 Evry cedex, France.
3 School of Management, University of Science and Technology of China, Hefei, P.R. China
4 School of Management, Xi’an Jiaotong University, Xi’an, 710049 Shaanxi Province, P.R. China
RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 733-748

This paper addresses single-machine scheduling problem with resource allocation and learning effect in the background of past-sequence-dependent (p-s-d) setup times. In the proposed model of this paper, the actual job processing times are dependent on learning effect and the amount of resource allocated, and the setup times are proportional to the length of the already processed jobs. The resource function used here is a general convex one. The optimal job sequence and the optimal amount of resource allocated to each job are determined jointly for the objective function yielded by a combination of the total completion time, total absolute differences in completion times, and the total resource consumption. Besides, we also discuss some extension and special cases of this problem. It is shown that all the problems under study are polynomially solvable while the complexity results are different.

DOI : 10.1051/ro/2016007
Classification : 90B35
Keywords: Scheduling, p-s-d setup times, resource allocation, learning effect

Zhu, Zhanguo 1, 2 ; Chu, Feng 2 ; Yu, Yugang 3 ; Sun, Linyan 4

1 College of Economics and Management, Nanjing Agricultural University, Nanjing 210095, P.R. China
2 Laboratoire d’informatique, biologie intégrative et systèmes complexes (IBISC), EA 4526, Université d’Evry Val d’Essonne, 91020 Evry cedex, France.
3 School of Management, University of Science and Technology of China, Hefei, P.R. China
4 School of Management, Xi’an Jiaotong University, Xi’an, 710049 Shaanxi Province, P.R. China 
@article{RO_2016__50_4-5_733_0,
     author = {Zhu, Zhanguo and Chu, Feng and Yu, Yugang and Sun, Linyan},
     title = {Single-machine past-sequence-dependent setup times scheduling with resource allocation and learning effect},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {733--748},
     year = {2016},
     publisher = {EDP Sciences},
     volume = {50},
     number = {4-5},
     doi = {10.1051/ro/2016007},
     zbl = {1353.90070},
     mrnumber = {3570527},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2016007/}
}
TY  - JOUR
AU  - Zhu, Zhanguo
AU  - Chu, Feng
AU  - Yu, Yugang
AU  - Sun, Linyan
TI  - Single-machine past-sequence-dependent setup times scheduling with resource allocation and learning effect
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 733
EP  - 748
VL  - 50
IS  - 4-5
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2016007/
DO  - 10.1051/ro/2016007
LA  - en
ID  - RO_2016__50_4-5_733_0
ER  - 
%0 Journal Article
%A Zhu, Zhanguo
%A Chu, Feng
%A Yu, Yugang
%A Sun, Linyan
%T Single-machine past-sequence-dependent setup times scheduling with resource allocation and learning effect
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 733-748
%V 50
%N 4-5
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ro/2016007/
%R 10.1051/ro/2016007
%G en
%F RO_2016__50_4-5_733_0
Zhu, Zhanguo; Chu, Feng; Yu, Yugang; Sun, Linyan. Single-machine past-sequence-dependent setup times scheduling with resource allocation and learning effect. RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 733-748. doi: 10.1051/ro/2016007

A. Agnetis, P.B. Mirchandani, D. Pacciarelli and A. Pacifici, Scheduling problems with two competing agents. Oper. Res. 52 (2004) 229–242. | Zbl | MR | DOI

A. Allahverdi, J.N.D. Gupta and T. Aldowaisan, A review of scheduling research involving setup considerations. OMEGA Int. J. Manage. Sci. 27 (1999) 219–239. | DOI

A. Allahverdi, C.T. Ng, T.C.E. Cheng and Y.K. Mikhail, A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187 (2008) 985–1032. | Zbl | MR | DOI

M. Asano and H. Ohta, Scheduling with shutdowns and sequence dependent set-up times. Int. J. Prod. Res. 37 (1999) 1661–1676. | Zbl | DOI

U. Bagchi, Simultaneous minimization of mean and variation of flow time and waiting time in single machine systems. Oper. Res. 37 (1989) 118–125. | Zbl | MR | DOI

D. Biskup, Single-machine scheduling with learning considerations. Eur. J. Oper. Res. 115 (1999) 173–178. | Zbl | DOI

D. Biskup, A state-of-the-art review on scheduling with learning effects. Eur. J. Oper. Res. 188 (2008) 315–329. | Zbl | MR | DOI

D. Biskup and J. Herrmann, Single-machine scheduling against due dates with past-sequence-dependent setup times. Eur. J. Oper. Res. 191 (2008) 587–592. | Zbl | MR | DOI

P. Brucker, Scheduling Algorithms, 3rd edition. Springer, Berlin (2001). | Zbl | MR

T.C.E. Cheng and A. Janiak, Resource optimal control in some single-machine scheduling problems. IEEE Trans. Autom. Control 39 (1994) 1243–1246. | Zbl | MR | DOI

T.C.E. Cheng and G.Q. Wang, Single machine scheduling with learning effect considerations. Ann. Oper. Res. 98 (2000) 273–290. | Zbl | MR | DOI

T.C.E. Cheng, Z.L. Chen and C.L. Li, Single-machine scheduling with trade-off between number of tardy jobs and resource allocation. Oper. Res. Lett. 19 (1996) 237–242. | Zbl | MR | DOI

T.C.E. Cheng, A. Janiak, M.Y. Kovalyov, Single machine batch scheduling with resource dependent setup and processing times. Eur. J. Oper. Res. 135 (2001) 177–183. | Zbl | MR | DOI

T.C.E. Cheng, W.C. Lee and C.C. Wu, Scheduling problems with deteriorating jobs and learning effects including proportional setup times. Comput. Ind. Eng. 58 (2010) 326–331. | DOI

R.L. Daniels and R.K. Sarin, Single machine scheduling with controllable processing times and number of jobs tardy. Oper. Res. 37 (1989) 981–984. | Zbl | DOI

C. de Snoo, Coordination in Planning and Scheduling-An Organizational and Behavioral Perspective. University of Groningen (2011). ISBN: 978-90-367-4502-4.

R.L. Graham, E.L. Lawler, J.K. Lenstra and A.R. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979) 287–326. | Zbl | MR | DOI

V.S. Gordon and A.A. Tarasevich, A note: Common due date assignment for a single machine scheduling with the rate-modifying activity. Comput. Oper. Res. 36 (2009) 325–328. | Zbl | MR | DOI

Y. He, M. Ji and T.C.E. Cheng, Single machine scheduling with a restricted rate-modifying activity. Naval Res. Logistics 52 (2005) 361–369. | Zbl | MR | DOI

A. Janiak and M.Y. Kovalyov, Single machine scheduling subject to deadlines and resource dependent processing times. Eur. J. Oper. Res. 94 (1996) 284–91. | Zbl | DOI

M. Kaspi and D. Shabtay, Convex resource allocation for minimizing the makespan in a single machine with job release dates. Comput. Oper. Res. 31 (2004) 1481–1489. | Zbl | MR | DOI

M. Kaspi and D. Shabtay, A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates. Comput. Oper. Res. 33 (2006) 3015–3033. | Zbl | DOI

C. Koulamas, A Note on single-machine scheduling with job-dependent learning effects. Eur. J. Oper. Res. 207 (2010) 1142–1143. | Zbl | MR | DOI

C. Koulamas and G. Kyparisis, Single-machine and two-machine flowshop scheduling with general learning functions. Eur. J. Oper. Res. 178 (2007) 402–407. | Zbl | MR | DOI

C. Koulamas and G.J. Kyparisis, Single-machine scheduling problems with past-sequence-dependent setup times. Eur. J. Oper. Res. 187 (2008) 68–72. | Zbl | MR | DOI

M.A. Kubzin and V.A. Strusevich, Planning machine maintenance in two-machine shop scheduling. Oper. Res. 54 (2006) 789–800. | Zbl | DOI

W.-H. Kuo and D.-L. Yang, Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect. Eur. J. Oper. Res. 174 (2006) 1184–1190. | Zbl | MR | DOI

W.-H. Kuo and D.-L. Yang, Single-machine scheduling with past-sequence-dependent setup and learning effects. Inf. Process. Lett. 102 (2007) 22–26. | Zbl | MR | DOI

C.-L. Lee and V.-J. Leon, Machine scheduling with a ratemodifying activity. Eur. J. Oper. Res. 129 (2001) 119–128. | Zbl | MR | DOI

W.-C. Lee and C.-C. Wu, Minimizing total completion time in a two-machine flowshop with a learning effect. Int. J. Prod. Econ. 88 (2004) 85–93. | DOI

J.Y.-T. Leung, M. Pinedo and G. Wan, Competitive two-agent scheduling and its applications. Oper. Res. 58 (2010) 458–469. | Zbl | MR | DOI

Y. Leyvand, D. Shabtay and G. Steiner, A unified approach for scheduling with convex resource consumption functions using positional penalties. Eur. J. Oper. Res. 206 (2010) 301–312. | Zbl | MR | DOI

Z. Liu and T.C.E. Cheng, Minimizing total completion time subject to job release dates and preemption penalties. J. Sched. 7 (2004) 313–327. | Zbl | MR | DOI

E.J. Lodree Jr. and C.D. Geiger, A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration. Eur. J. Oper. Res. 201 (2010) 644–648. | Zbl | MR | DOI

C.L. Monma, A. Schrijver, M.J. Todd and V.K. Wei, Convex resource allocation problems on directed acyclic graphs: Duality, complexity, special cases and extensions. Math. Oper. Res. 15 (1990) 736–748. | Zbl | MR | DOI

G. Mosheiov and J.B. Sidney, Scheduling with general job-dependent learning curves. Eur. J. Oper. Res. 147 (2003) 665–670. | Zbl | MR | DOI

G. Mosheiov and J.B. Sidney, Scheduling a deteriorating maintenance activity on a single machine. J. Oper. Res. Soc. 61 (2009) 882–887. | Zbl | DOI

D. Oron, Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times. Comput. Oper. Res. 35 (2008) 2071–2078. | Zbl | MR | DOI

M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer, New York, NY (2008). | Zbl | MR

D. Shabtay, M. Kaspi and G. Steiner, The no-wait two-machine flow-shop scheduling problem with convex resource-dependent processing times. IIE Trans. 39 (2007) 539–57. | DOI

D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times. Discrete Appl. Math. 155 (2007) 1643–1666. | Zbl | MR | DOI

N. Slack, S. Chambers and R. Johnston, Operations Management. Pearson Education, Harlow (2007).

D. Wang, M.-Z. Wang and J.-B. Wang, Single-machine scheduling with learning effect and resource-dependent processing times. Comput. Ind. Eng. 58 (2010) 458–462. | DOI

J.-B. Wang, Single-machine scheduling with past-sequence dependent setup times and time-dependent learning effect. Comput. Ind. Eng. 55 (2008) 584–591. | DOI

J.-B. Wang and J.-X. Li, Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects. Appl. Math. Model. 35 (2011) 1388–1395. | Zbl | MR | DOI

J.-B. Wang, D. Wang, L.-Y. Wang, L. Lin, N. Yin and W.-W. Wang, Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times. Comput. Math. Appl. 57 (2009) 9–16. | Zbl | MR | DOI

Y. Yin, T.C.E. Cheng, C.-C. Wu and S.-R. Cheng, Single-machine common due-date scheduling with batch delivery costs and resource-dependent processing times. Int. J. Prod. Res. 51 (2013) 5083–5099. | DOI

J.J. Yuan, T.C.E. Cheng and C.T. Ng, NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time. Eur. J. Oper. Res. 178 (2007) 631–633. | Zbl | MR | DOI

S.-J. Yang and D.-L. Yang, Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities. Comput. Math. Appl. 60 (2010) 2161–2169. | Zbl | MR | DOI

S.-J. Yang, D.-L. Yang and T.C.E. Cheng, Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance. Comput. Oper. Res. 37 (2010) 1510–1514. | Zbl | MR | DOI

C. Zhao and H. Tang, Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs. Comput. Ind. Eng. 59 (2010) 663–666. | DOI

C. Zhao, H. Tang and C. Cheng, Two-parallel machines scheduling with rate-modifying activities to minimize total completion time. Eur. J. Oper. Res. 198 (2009) 354–357. | Zbl | MR | DOI

Z. Zhu, F. Chu, L. Sun and M. Liu, Scheduling with resource allocation and past-sequence-dependent setup times including maintenance. International Conference on Networking, Sensing and Control (2011) 383–387.

Z. Zhu, L. Sun, F. Chu and M. Liu, Single-machine group scheduling with resource allocation and learning effect. Comput. Ind. Eng. 60 (2011) 148–157. | DOI

Z. Zhu, F. Chu, L. Sun and M. Liu, Single machine scheduling with resource allocation and learning effect considering the rate-modifying activity. Appl. Math. Model. 37 (2013) 5371–5380. | Zbl | MR | DOI

Cité par Sources :