A Heuristic Approach to Optimize Rental Costs in a No-Idle Two-Stage Flow Shop Scheduling Problem
Keywords:
Flow shop, setup time, no-idle constraint, optimal sequencing, scheduling optimization, rental cost minimizationAbstract
Scheduling is an important issue for maximizing resource utilization in manufacturing. This paper deals with the no-idle two-stage flow shop scheduling problem (FSSP), from the view point of minimizing the total rental costs. The no-idle constraint, which requires continuous machine operation, is a very important constraint in real-world manufacturing systems. While classical algorithms like Johnson's Algorithm and NEH heuristic have been widely used, they usually do not take into account the optimization of the rental costs under no-idle constraints. To fill this gap, a new heuristic algorithm for finding optimum job sequence in terms of total elapsed time and total rental cost is proposed. The resulting model incorporates setup times, probabilistic processing time and job weightage to improve scheduling efficiency. A mathematical model of the problem is given, and the computational experiments were carried out for different sizes of jobs. The performance of the proposed method is compared with the well-known heuristics such as Johnson's Algorithm, Palmer's Heuristic, NEH, and Nailwal's heuristic. Experimental findings reveal that the proposed heuristic consistently outperforms conventional methods, yielding lower rental costs and improved machine utilization efficiency.
References
Adiri, I. and Pohoryles, D. (1982). Flow shop no-idle or no-wait scheduling to minimize the sum of completion times. Naval Research Logistics, 29(3), 495–504.
Allahverdi, A., Gupta, J. N. D., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, Int. J. Mgmt Sci., 27(2), 219–239. https://doi.org/10.1016/S0305-0483(98)00042-5
Campbell, H. G., Dudek, R. A., & Smith, M. L. (1970). A heuristic algorithm for the n job, m machine sequencing problem. Management Science, 16(10), B630–B637.
Gupta, D., Goel, R., & Kaur, H. (2021). Optimizing rental cost with no idle constraints in two machines with weightage. Materials Today: Proceedings. https://doi.org/10.1016/j.matpr.2021.01.090
Gupta D., Shashi B., S. S. (2012). To Minimize The Rental Cost For 3- Stage Specially Structured Flow Shop Scheduling with Job Weightage. International Journal of Engineering Research and Applications (IJERA), 2(3), 912–916.
Ignall E, S. L. (1965). Application of the branch and bound technique to some flow-shop scheduling problems. Operations Research, 13(3), 400–412.
Jackson, J. R. (1956). An extension of Johnson’s results on job IDT scheduling. Naval Research Logistics Quarterly, 3(3), 201–203.
Johnson SM. (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval Research Logistics (NRL), 1(1), 61–68.
Kim, S. C., & Bobrowski, P. M. (1994). Impact of Sequence-Dependent Setup Time on Job Shop Scheduling Performance. Int. J. Prod. Res., 32(7), 1503–1520.
Kumari, S., Khurana, P., & Singla, S. (2021). RAP via constraint optimization genetic algorithm. Life Cycle Reliability and Safety Engineering, 10(4), 341–345. https://doi.org/10.1007/s41872-021-00173-0
Kumari, S., Khurana, P., & Singla, S. (2022). Behavior and profit analysis of a thresher plant under steady state. International Journal of System Assurance Engineering and Management, 13(1), 166–171. https://doi.org/10.1007/s13198-021-01183-y
Maggu, P. L., & Das, G. (1982). Weighted flow shop scheduling Problem. In Elements of Advanced Production Scheduling (1985th ed., pp. 105–111). United Publishers and Periodical distribution.
Miyazaki, S., Nishiyama, N. (1980). Analysis for minimizing weighted mean Minimizing rental cost in two stage flow shop, the processing time associated with probabilities including job block. Reflections de ERA, 1(2), 107–120.
Nawaz, M., Enscore Jr., E. E., & Ham, I. (1983). ‘A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. The International Journal of Management Science, 11(1), 91–95.
PALMER, D. S. (1985). Sequencing jobs through a multi stage process in the minimum total time-A quick method for obtaining a near optimum. Operations Research, 16, 101–107.
Singla, S., Kaur, H., & Gupta, D. (2023). Optimization of Rental Cost of Machines in Two Stage No-Idle Scheduling with Transportation Time and Weightage of Jobs. 2023 10th International Conference on Computing for Sustainable Global Development (INDIACom), 818–821. https://ieeexplore.ieee.org/document/10112467
Yoshida, T., & Hitomi, K. (1979). Optimal two-stage production scheduling with setup times separated. AIIE Transactions, 11(3), 261–263.
Baker, K. R. (1974). Introduction to sequencing and scheduling. John Wiley & Sons.
Ben-Daya, M., & Al-Fawzan, M. A. (1998). A tabu search approach for the flow shop scheduling problem. Journal of the Operational Research Society, 49(8), 840–848. https://doi.org/10.1057/palgrave.jors.2600565
Chakraborty, U. K., Laha, D., & Basu, A. (2009). A simulated annealing approach for solving no-idle permutation flow shop scheduling problems. International Journal of Advanced Manufacturing Technology, 42(9–10), 957–967. https://doi.org/10.1007/s00170-008-1652-1
Framinan, J. M., Gupta, J. N. D., & Leisten, R. (2004). A review and classification of heuristics for permutation flow-shop scheduling with makespan minimization. Journal of the Operational Research Society, 55(12), 1243–1255.
Gupta, J. N. D. (1972). Heuristic algorithms for multistage flowshop scheduling problem. AIIE Transactions, 4(1), 11–18.
Keller, A., & Nudelman, E. (2010). Minimizing makespan in a no-wait flow shop: A genetic algorithm approach. Computers & Operations Research, 37(3), 592–601.
Laha, D., & Chakraborty, U. K. (2009). A constructive heuristic for no-idle flow shop scheduling problems to minimize makespan. Applied Mathematics and Computation, 211(2), 503–511.
Pan, Q. K., & Ruiz, R. (2012). Local search methods for the flowshop scheduling problem with flowtime minimization. European Journal of Operational Research, 222(1), 31–43.
Ruiz, R., & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2), 479–494.
Wang, S., & Tang, L. (2011). A discrete artificial bee colony algorithm for no-wait flow shop scheduling problems with total flow time minimization. Computers & Operations Research, 38(6), 854–863.
Downloads
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
