Optimizing batch-processing operations with batch-position-based learning effects
RAIRO. Operations Research, Tome 55 (2021), pp. S253-S269

Motivated by applications in porcelain-making companies, we consider a type of optimization problems for batch-processing operations. In production, a single batch-processing machine with a fixed capacity is used to process jobs. Several jobs can be processed together if their total size is no more than the machine capacity. Batch-position-based learning effects are considered because workers become skillful gradually after they perform the processing task repeatedly. The actual processing time of a batch is a decreasing function of its position in production. The objective is to minimize makespan and we consider three different problems. In the first problem, jobs have identical sizes and we present an algorithm which can find optimal solutions in polynomial time. In the second problem, jobs have identical processing times and we show the problem is NP-hard in the strong sense. We propose an approximation algorithm with an absolute performance guarantee of 1.5 and asymptotic performance guarantee of 1.223. In the third problem, jobs have non-identical sizes and processing times simultaneously. We propose an algorithm with an absolute and asymptotic performance guarantee of 2. Besides, we present the evolution of the performance guarantee and provide managerial insights for decision makers of manufacturing companies.

DOI : 10.1051/ro/2019108
Classification : 90C97
Keywords: Optimization, learning effects, batch processing, scheduling, heuristics 
@article{RO_2021__55_S1_S253_0,
     author = {Tai, Leilei},
     title = {Optimizing batch-processing operations with batch-position-based learning effects},
     journal = {RAIRO. Operations Research},
     pages = {S253--S269},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2019108},
     mrnumber = {4237385},
     zbl = {1472.90039},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2019108/}
}
TY  - JOUR
AU  - Tai, Leilei
TI  - Optimizing batch-processing operations with batch-position-based learning effects
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S253
EP  - S269
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2019108/
DO  - 10.1051/ro/2019108
LA  - en
ID  - RO_2021__55_S1_S253_0
ER  - 
%0 Journal Article
%A Tai, Leilei
%T Optimizing batch-processing operations with batch-position-based learning effects
%J RAIRO. Operations Research
%D 2021
%P S253-S269
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2019108/
%R 10.1051/ro/2019108
%G en
%F RO_2021__55_S1_S253_0
Tai, Leilei. Optimizing batch-processing operations with batch-position-based learning effects. RAIRO. Operations Research, Tome 55 (2021), pp. S253-S269. doi: 10.1051/ro/2019108

[1] S. Akiyoshi, V. S. Natalia and A. S. Vitaly, Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines. INFORMS J. Comput. 28 (2016) 148–161. | MR | Zbl | DOI

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

[3] T. C. E. Cheng, C. T. Ng, J. J. Yuan and Z. H. Liu, Single machine parallel batch scheduling subject to precedence constraints. Nav. Res. Logist. 51 (2004) 949–958. | MR | Zbl | DOI

[4] B. Y. Cheng, J. Y. T. Leung, K. Li and S. L. Yang, Single batch machine scheduling with deliveries. Nav. Res. Logist. 62 (2015) 470–482. | MR | Zbl | DOI

[5] J. R. Dejong, The effects of increasing skill on cycle time and its consequences for time standards. Economics 1 (1957) 51–60.

[6] G. Dosa, R. Li, X. Han and Z. Tuza, Tight absolute bound for first fit decreasing bin packing: FFD(L) 11/9OPT(L) + 6/9. Theor. Comput. Sci. 510 (2013) 13–61. | MR | Zbl | DOI

[7] D. Giglio, Optimal control strategies for single-machine family scheduling with sequence-dependent batch setup and controllable processing times. J. Sched. 18 (2015) 525–543. | MR | Zbl | DOI

[8] N. P. A. Hidayat, A. Cakravastia, T. M. A. A. Samadhi and A. H. Halim, A batch scheduling model for m heterogeneous batch processor. Int. J. Prod. Res. 54 (2016) 1170–1185, | DOI

[9] X. Huang, M. Z. Wang and P. Ji, Parallel machines scheduling with deteriorating and learning effects. Optim. Lett. 8 (2014) 493–500. | MR | Zbl | DOI

[10] M. Ji, D. Yao, Q. Yang and T. C. E. Cheng, Machine scheduling with DeJongs learning effect. Comput. Ind. Eng. 80 (2014) 195–200. | DOI

[11] Z. Jiang, F. Chen and H. Kang, Single-machine scheduling problems with actual time-dependent and job-dependent learning effect. Eur. J. Oper. Res. 115 (2013) 173–178.

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

[13] P. J. Lai and W. C. Lee, Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects. OMEGA Int. J. Manage. Sci. 39 (2011) 467–471. | DOI

[14] W. C. Lee, Scheduling with general position-based learning curves. Inf. Sci. 181 (2011) 5515–5522. | MR | Zbl | DOI

[15] W. C. Lee, C. C. Wu and P. H. Hsu, A single-machine learning effect scheduling problem with release times. OMEGA Int. J. Manage. Sci. 28 (2010) 3–11. | DOI

[16] Y. Li, Combined scheduling algorithm for re-entrant batch-processing machines in semiconductor wafer manufacturing. Int. J. Prod. Res. 53 (2015) 1866–1879. | DOI

[17] M. Li and N. C. Petruzzi, Demand uncertainty reduction in decentralized supply chains. Prod. Oper. Manage. 26 (2017) 156–161. | DOI

[18] M. Liu, Parallel-machine scheduling with past-sequence-dependent delivery times and learning effect. Appl. Math. Model. 37 (2013) 9630–9633. | MR | Zbl | DOI

[19] L. L. Liu, C. T. Ng and T. C. E. Cheng, Scheduling jobs with release dates on parallel batch processing machines. Discrete Appl. Math. 157 (2009) 1825–1830. | MR | Zbl | DOI

[20] D. Okolowski and S. Gawiejnowicz, Exact and heuristic algorithms for parallel-machine scheduling with DeJongs learning effect. Comput. Ind. Eng. 59 (2010) 272–279. | DOI

[21] M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer (2008). | MR | Zbl

[22] J. Qian and G. Steiner, Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine. Eur. J. Oper. Res. 225 (2013) 547–551. | MR | Zbl | DOI

[23] Y. Tan and J. Carrillo, Strategic analysis of the agency model for digital goods. Prod. Oper. Manage. 24 (2017) 724–741. | DOI

[24] Y. Tan, J. Carrillo and H. K. Cheng, The agency model for digital goods. Decis. Sci. 47 (2016) 628–660. | DOI

[25] L. X. Tang, G. S. Wang and Z. L. Chen, Integrated charge batching and casting width selection at baosteel. Oper. Res. 62 (2014) 772–787. | Zbl | DOI

[26] T. T. Tran, A. Araujo and J. C. Beck, Decomposition methods for the parallel machine scheduling problem with setups. INFORMS J. Comput. 28 (2016) 83–95. | MR | Zbl | DOI

[27] J. Q. Wang and J. Y. T. Leung, Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan. Int. J. Prod. Econ. 156 (2014) 325–331. | DOI

[28] H. Wiebke, K. G. Felix, M. H. Rolf and L. E. Marco, Integrated sequencing and scheduling in coil coating. Manage. Sci. 57 (2011) 647–666. | Zbl

[29] D. L. Yang and W. H. Kuo, A single-machine scheduling problem with learning effects in intermittent batch production. Comput. Ind. Eng. 57 (2009) 762–765. | DOI

Cité par Sources :