A Two-Machine Flow Shop Batch Scheduling Model to Minimize Total Actual Flow Time
:
https://doi.org/10.9744/jti.25.2.179-194
Keywords:
Batch, scheduling, two-machine, flowshop, actual flow timeAbstract
This study introduces a scheduling model for a two-machine flow shop batch system to minimize the actual flow time. In this system, two machines are responsible for processing raw materials and producing finished products, with a single bottleneck machine. The entity overseeing the manufacturing process organizes demand units into batches, ensures the accurate and timely arrival of raw materials, and delivers all finished products punctually to meet an expected due date. The study addresses crucial challenges, including determining the optimal number of batches, sizes, and sequences to achieve the specified objective. The analysis adopted an algorithm grounded in the Lagrange relaxation method to tackle these challenges. Moreover, the algorithm is operated by identifying the bottleneck machine as a scheduling reference and determining the appropriate number of batches and sizes. The analysis showed the efficacy of the developed algorithm by using Johnson's rule for making batch sequence decisions through numerical experiments conducted across 1000 cases. The results showed a 1.44% to 4.43% improvement in efficiency compared to previous research, accompanied by a 2–8 times reduction in computational time.
References
A. Allahverd, “A survey of scheduling problems with uncertain interval/bounded processing/setup times,” Journal of Project Management, vol. 7, no. 4, pp. 255–264, 2022, doi: 10.5267/j.jpm.2022.3.003.
A. Allahverdi, “A survey of scheduling problems with no-wait in process,” European Journal of Operational Research, vol. 255, no. 3, pp. 665–686, 2016, doi: 10.1016/j.ejor.2016.05.036.
A. Allahverdi, C. T. Ng, T. C. E. Cheng, and M. Y. Kovalyov, “A survey of scheduling problems with setup times or costs,” European Journal of Operational Research, vol. 187, no. 3, pp. 985–1032, 2008, doi: 10.1016/j.ejor.2006.06.060.
B. Çaliş and S. Bulkan, “A research survey: review of AI solution strategies of job shop scheduling problem,” Journal of Intelligent Manufacturing, vol. 26, no. 5, pp. 961–973, 2015, doi: 10.1007/s10845-013-0837-8.
J. W. Fowler and L. Mönch, “A survey of scheduling with parallel batch (p-batch) processing,” European Journal of Operational Research, vol. 298, no. 1, pp. 1–24, 2022, doi: 10.1016/j.ejor.2021.06.012.
S. Hartmann and D. Briskorn, “An updated survey of variants and extensions of the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 297, no. 1, pp. 1–14, 2022, doi: 10.1016/j.ejor.2021.05.004.
B. M. T. Lin, “Fabrication scheduling on a single machine with due date constraints,” European Journal of Operational Research, vol. 136, no. 1, pp. 95–105, 2002, doi: 10.1016/S0377-2217(01)00036-4.
S. Reza Hejazi and S. Saghafian, “Flowshop-scheduling problems with makespan criterion: A review,” International Journal of Production Research, vol. 43, no. 14, pp. 2895–2929, 2005, doi: 10.1080/0020754050056417.
D. Shabtay and G. Steiner, “A survey of scheduling with controllable processing times,” Discrete Applied Mathematics, vol. 155, no. 13, pp. 1643–1666, 2007, doi: 10.1016/j.dam.2007.02.003.
M. Sterna, “Late and early work scheduling: A survey,” Omega (United Kingdom), vol. 104, no. xxxx, 2021, doi: 10.1016/j.omega.2021.102453.
S. Suprayogi and V. Valentine, “Teknik Relaksasi Lagrange untuk Penjadwalan Pekerjaan Majemuk dengan Penggunaan Sumberdaya Simultan,” Jurnal Teknik Industri: Jurnal Keilmuan dan Terapan Teknik Industri, UK. Petra, vol. 17, no. 2, pp. 71–80, Dec. 2015, doi: 10.9744/jti.17.2.71-80.
K. R. Baker, Introduction to Sequencing and Scheduling. New York: JOHN WILEY & SONS, INC, 1974.
S. M. Johnson, “Optimal two‐and three‐stage production schedules with setup times included,” Naval research logistics quarterly, vol. 1, no. 1, pp. 61–68, 1954.
H. G. Campbell, R. A. Dudek, and M. L. Smith, “A heuristic algorithm for the n job, m machine sequencing problem,” Management science, vol. 16, no. 10, p. B-630, 1970.
P. Brucker, B. Jurisch, and B. Sievers, “A branch and bound algorithm for the job-shop scheduling problem,” Discrete Applied Mathematics, vol. 49, no. 1–3, pp. 107–127, 1994, doi: 10.1016/0166-218X(94)90204-6.
R. Yusriski, R. Pardiyono, Zahedi, S. Rahmawati, and A. Ramdhani, “Dynamic flexible flow shop scheduling with theory of constraint and time window approach to minimize mean tardiness,” AIP Conference Proceedings, vol. 2510, no. 1, p. 40026, Oct. 2023, doi: 10.1063/5.0128591.
C. Blum and M. Sampels, “An ant colony optimization algorithm for shop scheduling problems,” Journal of Mathematical Modelling and Algorithms, vol. 3, no. 3, pp. 285–308, 2004, doi: 10.1023/B:JMMA.0000038614.39977.6f.
T. Murata, H. Ishibuchi, and H. Tanaka, “Multiobjective genetic algorithm and its application to flowshop scheduling,” Computers and Industrial Engineering, vol. 30, pp. 957–968, 1996, doi: http://dx.doi.org/10.1016/0360-8352(96)00045-9.
E. Nowicki and C. Smutnicki, “A fast tabu search algorithm for the permutation flow-shop problem,” European Journal of Operational Research, vol. 91, no. 1, pp. 160–175, 1996, doi: 10.1016/0377-2217(95)00037-2.
B. M. T. Lin and T. C. E. Cheng, “Batch scheduling in the no-wait two-machine flowshop to minimize the makespan,” Computers & Operations Research, vol. 28, no. 7, pp. 613–624, 2001, doi: https://doi.org/10.1016/S0305-0548(99)00138-0.
M. Pranzo, “Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times,” European Journal of Operational Research, vol. 153, no. 3, pp. 581–592, 2004, doi: https://doi.org/10.1016/S0377-2217(03)00264-9.
L. Ben-Dati, G. Mosheiov, and D. Oron, “Batch scheduling on two-machine flowshop with machine-dependent setup times,” in Advances in Operations Research, 2009, p. 10. doi: 10.1155/2009/153910.
A. H. Halim, S. Miyazaki, and H. Ohta, “Batch-scheduling problems to minimize actual flow times of parts through the shop under JIT environment,” European Journal of Operational Research, vol. 72, no. 3, pp. 529–544, 1994, doi: 10.1016/0377-2217(94)90421-9.
D. Kurniawan, R. Yusriski, M. M. Isnaini, M. Anas, and A. H. Halim, “A flow shop batch scheduling model with part deterioration and operator learning-forgetting effects to minimize total actual flow time,” in Proceedings of the Second Asia Pacific International Conference on Industrial Engineering and Operations Management, 2021, pp. 644–655.
A. S. Indrapriyatna, S. Suprayogi, B. P. Iskandar, and A. H. Halim, “Model penjadwalan batch pada satu mesin yang mengalami deteriorasi untuk minimasi total biaya simpan dan biaya kualitas,” Jurnal Teknik Industri: Jurnal Keilmuan dan Terapan Teknik Industri, vol. 10, no. 1, pp. 26–37, Jul. 2008, doi: 10.9744/jti.10.1.26-37.
R. Yusriski, Sukoyo, T. M. A. A. Samadhi, and A. H. Halim, “An integer batch scheduling model for a single machine with simultaneous learning and deterioration effects to minimize total actual flow time,” IOP Conference Series: Materials Science and Engineering, vol. 114, no. 1, 2016, doi: 10.1088/1757-899X/114/1/012073.
R. Yusriski, B. Astuti, D. Biksono, and T. A. Wardani, “A single machine multi-job integer batch scheduling problem with multi due date to minimize total actual flow time,” Decision Science Letters, vol. 10, no. 3, pp. 231–240, 2021, doi: 10.5267/j.dsl.2021.4.002.
R. Yusriski, S. Sukoyo, T. M. A. A. Samadhi, and A. H. Halim, “Integer batch scheduling problems for a single-machine with simultaneous effects of learning and forgetting to minimize total actual flow time,” International Journal of Industrial Engineering Computations, vol. 6, no. 3, pp. 365–378, 2015, doi: 10.5267/j.ijiec.2015.2.005.
Zahedi, Rojali, and R. Yusriski, “Stepwise optimization for model of integrated batch production and maintenance scheduling for single item processed on flow shop with two machines in jit environment,” Procedia Computer Science, vol. 116, pp. 408–420, 2017, doi: 10.1016/j.procs.2017.10.081.
Zahedi, T. A. Samadhi, Suprayogi, and A. H. Halim, “Model integrasi penjadwalan produksi batch dan penjadwalan perawatan dengan kendala due date,” Jurnal Teknik Industri: Jurnal Keilmuan dan Terapan Teknik Industri, UK. Petra, vol. 16, no. 2, pp. 75–83, 2014, doi: 10.9744/jti.16.2.73-82.
Z. Zahedi, A. Salim, R. Yusriski, and H. Haris, “Optimization of an integrated batch production and maintenance scheduling on flow shop with two machines,” International Journal of Industrial Engineering Computations, vol. 10, no. 2, pp. 225–238, 2019, doi: 10.5267/j.ijiec.2018.7.001.
A. Hakim Halim and H. Ohta, “Batch-scheduling problems through the flowshop with both receiving and delivery just in time,” International Journal of Production Research, vol. 31, no. 8, pp. 1943–1955, 1993, doi: 10.1080/00207549308956833.
R. Maulidya, Suprayogi, R. Wangsaputra, and A. H. Halim, “Batch scheduling for hybrid assembly differentiation flow shop to minimize total actual flow time,” IOP Conference Series: Materials Science and Engineering, vol. 319, no. 1, 2018, doi: 10.1088/1757-899X/319/1/012042.
P. P. Suryadhini, S. Sukoyo, S. Suprayogi, and A. H. Halim, “A batch scheduling model for a three-stage flow shop with job and batch processors considering a sampling inspection to minimize expected total actual flow time,” Journal of Industrial Engineering and Management, vol. 14, no. 3, pp. 520–537, 2021, doi: 10.3926/JIEM.3438.
H. Triha, A. S. Indrapriyatna, J. Jonrinaldi, and B. Yuliandra, “Algoritma penentuan ukuran batch integer pada penjadwalan flowshop satu mesin,” Jurnal Optimasi Sistem Industri, vol. 15, no. 1, p. 1, 2016, doi: 10.25077/josi.v15.n1.p1-15.2016.
R. Yusriski, B. Astuti, M. Ilham, and Zahedi, “Integrated batch production and multiple preventive maintenance scheduling on a single machine to minimize total actual flow time,” IOP Conference Series: Materials Science and Engineering, vol. 598, no. 1, 2019, doi: 10.1088/1757-899X/598/1/012083.
R. Yusriski, B. Astuti, Sukoyo, T. M. A. A. Samadhi, and A. H. Halim, “Integer batch scheduling problems for a single-machine to minimize total actual flow time,” Procedia Manufacturing, vol. 2, no. February, pp. 118–123, 2015, doi: 10.1016/j.promfg.2015.07.021.
A. Ageev, “Approximating the 2-machine flow shop problem with exact delays taking two values,” Journal of Global Optimization, vol. 76, no. 3, pp. 491–497, 2020, doi: 10.1007/s10898-019-00775-0.
B. C. Choi and M. J. Park, “Correction to: Two-machine flow shop scheduling with convex resource consumption functions,” Optimization Letters, vol. 17, no. 5, pp. 1261–1262, 2023, doi: 10.1007/s11590-023-01982-1.
S. A. Mansouri, E. Aktas, and U. Besikci, “Green scheduling of a two-machine flowshop: Trade-off between makespan and energy consumption,” European Journal of Operational Research, vol. 248, no. 3, pp. 772–788, 2016, doi: https://doi.org/10.1016/j.ejor.2015.08.064.
M.-J. Park, B.-C. Choi, Y. Min, and K. M. Kim, “Two-machine ordered flow shop scheduling with generalized due dates,” Asia-Pacific Journal of Operational Research, vol. 37, no. 1, pp. 1–16, 2020, [Online]. Available: https://api.semanticscholar.org/CorpusID:202126506
Downloads
Published
How to Cite
Issue
Section
License
Articles published in the Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri will be Open-Access articles distributed under the terms and conditions of the Creative Commons Attribution License (CC BY).
This work is licensed under a Creative Commons Attribution License (CC BY).
