Minimizing Total Weighted Tardiness in a Flexible Flowshop Environment Considering Batch Processing Machines
Authors
Abstract
Scheduling in production environments is used as a competitive tool to improve efficiency and respond to customer requests. In this paper, a scheduling problem is investigated in a three-stage flexible flowshop environment with the consideration of blocking and batch processing. This problem has been inspired by the charging and packaging line of a large battery manufacturer. In this environment, the first and third stages involve a single processor machine, and the second one consists of m identical parallel batch processing machines. The objective is to minimize the total weighted tardiness of the received orders.Given the lack of consideration of this problem in the literature, first, a mathematical programming model is presented for the problem. Also, due to the NP-hardness of the problem, a variable neighborhood search algorithm and a memetic algorithm are developed to solve it. The computational results show that the variable neighborhood search algorithm can solve instances up to 1200 orders and 15 machines with an average deviation of about 1.9%, relative to the best solution of the two algorithms, and the memetic algorithm can solve instances up to 1200 orders and 15 machines with an average deviation of about 7.8%, as compared e to the best solution of the two algorithms. In general, computational results show the better performance of the variable neighborhood search algorithm in comparison to the memetic algorithm.
Keywords
1. Ikura, Y., and Gimple, M., “Efficient Scheduling Algorithms for a Single Batch Processing Machine”, Operations Research Letters, Vol. 5, pp. 61-65, 1986.
2. Lee, C.-Y., Uzsoy, R., and Martin-Vega, L.A., “Efficient Algorithms for Scheduling Semiconductor Burn-in Operations”, Operations Research, Vol. 40, pp. 764-775, 1992.
3. Uzsoy, R., “Scheduling Batch Processing Machines with Incompatible Job Families”, International Journal of Production Research, Vol. 33, pp. 2685-2708, 1995.
4. Damodaran, P., and Velez-Gallego, M. C., “Heuristics for Makespan Minimization on Parallel Batch Processing Machines with Unequal Job Ready Times”, The International Journal of Advanced Manufacturing Technology, Vol. 49, pp. 1119-1128, 2010.
5. Hulett, M., Damodaran, P., and Amouie, M., “Scheduling Non-Identical Parallel Batch Processing Machines to Minimize Total Weighted Tardiness Using Particle Swarm Optimization”, Computers & Industrial Engineering, Vol. 113, pp. 425-436, 2017.
6. Luo, H., Huang, G. Q., Zhang, Y., Dai, Q., and Chen, X., “Two-Stage Hybrid Batching Flowshop Scheduling with Blocking and Machine Availability Constraints Using Genetic Algorithm”, Robotics and Computer-Integrated Manufacturing, Vol. 25, pp. 962-971, 2009.
7. Balasubramanian, H., Mönch, L., Fowler, J., and Pfund, M., “Genetic Algorithm Based Scheduling of Parallel Batch Machines with Incompatible Job Families to Minimize Total Weighted Tardiness”, International Journal of Production Research, Vol. 42, pp. 1621-1638, 2004.
8. Mathirajan, M., and Sivakumar, A., “Minimizing Total Weighted Tardiness on Heterogeneous Batch Processing Machines with Incompatible Job Families”, The International Journal of Advanced Manufacturing Technology, Vol. 28, pp. 1038, 2006.
9. Almeder, C., and Mönch, L., “Metaheuristics for Scheduling Jobs with Incompatible Families on Parallel Batching Machines”, Journal of the Operational Research Society, Vol. 62, pp. 2083-2096, 2011.
10. Chiang, T.-C., Cheng, H.-C., and Fu, L.-C., “A Memetic Algorithm for Minimizing Total Weighted Tardiness on Parallel Batch Machines with Incompatible Job Families and Dynamic Job Arrival”, Computers & Operations Research, Vol. 37, pp. 2257-2269, 2010.
11. Chou, F.-D., “Minimising the Total Weighted Tardiness for Non-Identical Parallel Batch Processing Machines with Job Release Times and Non-Identical Job Sizes”, European Journal of Industrial Engineering, Vol. 7, pp. 529-557, 2013.
12. Mathirajan, M., Bhargav, V., and Ramachandran, V., “Minimizing Total Weighted Tardiness on a Batch-Processing Machine with Non-Agreeable Release Times and Due Dates”, The International Journal of Advanced Manufacturing Technology, Vol. 48, pp. 1133-1148, 2010.
13. Shi, Z., Huang, Z., and Shi, L., “Customer Order Scheduling on Batch Processing Machines with Incompatible Job Families”, International Journal of Production Research, Vol. 56, pp. 795-808, 2018.
14. Vivek, P., Saravanan, R., Chandrasekaran, M., Pugazhenthi, R., and Vairavel, M., “A Critical-Machine Based Heuristic for HFS Batch Scheduling”, International Journal of Mechanical Engineering and Technology, Vol. 9, pp. 105-119, 2018.
15. Zeng, Z., Hong, M., Man, Y., Li, J., Zhang, Y., and Liu, H., “Multi-Object Optimization of Flexible Flow Shop Scheduling with Batch Process — Consideration Total Electricity Consumption and Material Wastage”, Journal of Cleaner Production, Vol. 183, pp. 925-939, 2018.
16. Tan, Y., Mönch, L., and Fowler, J. W., “A Hybrid Scheduling Approach for a Two-Stage Flexible Flow Shop with Batch Processing Machines”, Journal of Scheduling, Vol. 21, pp. 209-226, 2018.
17. Graham, R. L., Lawler, E. L., Lenstra, J. K., and Kan, A. R., “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey”, Annals of Discrete Mathematics, Vol. 5, pp. 287-326, 1979.
18. Sawik, T., “Mixed Integer Programming for Scheduling Flexible Flow Lines with Limited Intermediate Buffers”, Mathematical and Computer Modelling, Vol. 31, pp. 39-52, 2000.
19. Mladenović, N., and Hansen, P., “Variable Neighborhood Search”, Computers & Operations Research, Vol. 24, pp. 1097-1100, 1997.
20. Parsa, N. R., Karimi, B., and Kashan, A. H., “A Branch and Price Algorithm to Minimize Makespan on a Single Batch Processing Machine with Non-Identical Job Sizes”, Computers & Operations Research, Vol. 37, pp. 1720-1730, 2010
2. Lee, C.-Y., Uzsoy, R., and Martin-Vega, L.A., “Efficient Algorithms for Scheduling Semiconductor Burn-in Operations”, Operations Research, Vol. 40, pp. 764-775, 1992.
3. Uzsoy, R., “Scheduling Batch Processing Machines with Incompatible Job Families”, International Journal of Production Research, Vol. 33, pp. 2685-2708, 1995.
4. Damodaran, P., and Velez-Gallego, M. C., “Heuristics for Makespan Minimization on Parallel Batch Processing Machines with Unequal Job Ready Times”, The International Journal of Advanced Manufacturing Technology, Vol. 49, pp. 1119-1128, 2010.
5. Hulett, M., Damodaran, P., and Amouie, M., “Scheduling Non-Identical Parallel Batch Processing Machines to Minimize Total Weighted Tardiness Using Particle Swarm Optimization”, Computers & Industrial Engineering, Vol. 113, pp. 425-436, 2017.
6. Luo, H., Huang, G. Q., Zhang, Y., Dai, Q., and Chen, X., “Two-Stage Hybrid Batching Flowshop Scheduling with Blocking and Machine Availability Constraints Using Genetic Algorithm”, Robotics and Computer-Integrated Manufacturing, Vol. 25, pp. 962-971, 2009.
7. Balasubramanian, H., Mönch, L., Fowler, J., and Pfund, M., “Genetic Algorithm Based Scheduling of Parallel Batch Machines with Incompatible Job Families to Minimize Total Weighted Tardiness”, International Journal of Production Research, Vol. 42, pp. 1621-1638, 2004.
8. Mathirajan, M., and Sivakumar, A., “Minimizing Total Weighted Tardiness on Heterogeneous Batch Processing Machines with Incompatible Job Families”, The International Journal of Advanced Manufacturing Technology, Vol. 28, pp. 1038, 2006.
9. Almeder, C., and Mönch, L., “Metaheuristics for Scheduling Jobs with Incompatible Families on Parallel Batching Machines”, Journal of the Operational Research Society, Vol. 62, pp. 2083-2096, 2011.
10. Chiang, T.-C., Cheng, H.-C., and Fu, L.-C., “A Memetic Algorithm for Minimizing Total Weighted Tardiness on Parallel Batch Machines with Incompatible Job Families and Dynamic Job Arrival”, Computers & Operations Research, Vol. 37, pp. 2257-2269, 2010.
11. Chou, F.-D., “Minimising the Total Weighted Tardiness for Non-Identical Parallel Batch Processing Machines with Job Release Times and Non-Identical Job Sizes”, European Journal of Industrial Engineering, Vol. 7, pp. 529-557, 2013.
12. Mathirajan, M., Bhargav, V., and Ramachandran, V., “Minimizing Total Weighted Tardiness on a Batch-Processing Machine with Non-Agreeable Release Times and Due Dates”, The International Journal of Advanced Manufacturing Technology, Vol. 48, pp. 1133-1148, 2010.
13. Shi, Z., Huang, Z., and Shi, L., “Customer Order Scheduling on Batch Processing Machines with Incompatible Job Families”, International Journal of Production Research, Vol. 56, pp. 795-808, 2018.
14. Vivek, P., Saravanan, R., Chandrasekaran, M., Pugazhenthi, R., and Vairavel, M., “A Critical-Machine Based Heuristic for HFS Batch Scheduling”, International Journal of Mechanical Engineering and Technology, Vol. 9, pp. 105-119, 2018.
15. Zeng, Z., Hong, M., Man, Y., Li, J., Zhang, Y., and Liu, H., “Multi-Object Optimization of Flexible Flow Shop Scheduling with Batch Process — Consideration Total Electricity Consumption and Material Wastage”, Journal of Cleaner Production, Vol. 183, pp. 925-939, 2018.
16. Tan, Y., Mönch, L., and Fowler, J. W., “A Hybrid Scheduling Approach for a Two-Stage Flexible Flow Shop with Batch Processing Machines”, Journal of Scheduling, Vol. 21, pp. 209-226, 2018.
17. Graham, R. L., Lawler, E. L., Lenstra, J. K., and Kan, A. R., “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey”, Annals of Discrete Mathematics, Vol. 5, pp. 287-326, 1979.
18. Sawik, T., “Mixed Integer Programming for Scheduling Flexible Flow Lines with Limited Intermediate Buffers”, Mathematical and Computer Modelling, Vol. 31, pp. 39-52, 2000.
19. Mladenović, N., and Hansen, P., “Variable Neighborhood Search”, Computers & Operations Research, Vol. 24, pp. 1097-1100, 1997.
20. Parsa, N. R., Karimi, B., and Kashan, A. H., “A Branch and Price Algorithm to Minimize Makespan on a Single Batch Processing Machine with Non-Identical Job Sizes”, Computers & Operations Research, Vol. 37, pp. 1720-1730, 2010
)