A new mathematical model for single machine batch scheduling problem for minimizing maximum lateness with deteriorating jobs

Haddad, H.; Ghanbari, P.; Moghaddam, A.

Abstract: This paper presents a mathematical model for the problem of minimizing the maximum lateness on a single machine when the deteriorated jobs are delivered to each customer in various size batches. In reality, this issue may happen within a supply chain in which delivering goods to customers entails cost. Under such situation, keeping completed jobs to deliver in batches may result in reducing delivery costs. In literature review of batch scheduling, minimizing the maximum lateness is known as NP-Hard problem; therefore the present issue aiming at minimizing the costs of delivering, in addition to the aforementioned objective function, remains an NP-Hard problem. In order to solve the proposed model, a Simulation annealing meta-heuristic is used, where the parameters are calibrated by Taguchi approach and the results are compared to the global optimal values generated by Lingo 10 software. Furthermore, in order to check the efficiency of proposed method to solve larger scales of problem, a lower bound is generated. The results are also analyzed based on the effective factors of the problem. Computational study validates the efficiency and the accuracy of the presented model.

How to cite this paper

 Haddad, H., Ghanbari, P & Moghaddam, A. (2012). A new mathematical model for single machine batch scheduling problem for minimizing maximum lateness with deteriorating jobs.International Journal of Industrial Engineering Computations , 3(2), 253-264.

References

Al-Anzi, F. S., Allahverdi, A., & Kovalyov, M.Y. (2007). Batching deteriorating items with applications in computer communication and reverse logistics. European Journal of Operational Research, 182(3), 1002–1011.

Albers, S., & Brucker, P. (1993). The complexity of one -machine batching problems. Discrete Applied Mathematics, 47(2), 87–107.

Azizoglu, M., & Webster, S. (2001). Scheduling a batch processing machine with incompatible job families. Computers & Industrial Engineering, 39, 325–335.

Baptiste, P. (2000). Batching identical jobs. Mathematical Methods of Operations Research, 52, 355–367.

Browne, S., & Yechiali, U. (1990). Scheduling deteriorating jobs on a single processor. Operations Research, 38(3), 495–498.

Chen, B., Deng, X.T., & Zang, W.A. (2004). On-line scheduling a batch processing system to minimize total weighted job completion time. Journal of Combinatorial Optimization, 8, 85–95.

Cheng, T.C.E., & Ji, M. (2010). Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan. European Journal of Operational Research, 202(1), 90–98.

Coffman, E., Yannakakis, M., Magazine, M.J., & Santos, C 1990). Batch sizing and sequencing on a single machine. Annals of Operations Research, 26, 135–147.

Huang, X., Wang, J.B., & Wang, X. R. (2010). A generalization for single-machine scheduling with deteriorating jobs to minimize earliness penalties. International Journal of Advance Manufacturing Technology, 47(9-12), 1225–1230.

Lu, L.F., & Yuan, J.J. (2007). The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard. European Journal of Operational Research, 177, 1302–1309.

Mahdavi Mazdeh, M., Hamidinia, A., & Karamouzian, A. (2011a). A mathematical model for weighted tardy jobs scheduling problem with a batched delivery system. International Journal of Industrial Engineering Computations, 2, 491-489.

Mahdavi Mazdeh, M., Sarhadi, M., & Hindi, KS. (2007). A branch-and-bound algorithm for single-machine scheduling with batch delivery minimizing flow times and delivery costs. European Journal of Operational Research, 183, 74–86

Mahdavi Mazdeh, M., Shashaani, S ., Ashouri, A. , & Hindi, K.S. (2011b). Single-machine batch scheduling minimizing weighted flow times and delivery costs. Applied Mathematical Modeling, 35, 563–570.

Mosheiov, G. (1994). Scheduling jobs under simple linear deterioration, Computers and Operations Research, 21, 653–659.

Ng, C.T., Cheng, T.C.E., Yuan, J.J., & Liu, Z.H. (2003). On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times. Operations Research Letters, 31, 323 – 326.

Ng, CT., Cheng, TCE., & Yuan, JJ. (2002). A note on the single machine serial batching scheduling problem to minimize maximum lateness with precedence constraints. Operations Research Letters, 30, 66 – 68.

Nong, Q., Ng, CT., & Cheng, TCE. (2008). The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan. Operations Research Letters, 36, 61 – 66.

Nong, Q., Yuan, JJ., Fu, R., Lin, L., & Tian, J.I. (2008). The single-machine parallel-batching on-line scheduling problem with family jobs to minimize makespan. International Journal of Production Economics, 111, 435–440.

Potts, C.N., & Kovalyov, M.Y. (2000). Scheduling with batching: a review. European Journal of Operational Research, 120, 228–249.

Tian, J., Fu, R., & Yuan, J. (2007). On-line scheduling with delivery time on a single batch machine. Theoretical Computer Science, 374, 49–57.

Van Laarhoven, P.J.M., & Aarts, E.H.(1988). Simulated Annealing: Theory and Applications. Kluwer Academic Publishers, Dordrecht.

Wang, D., & Wang, J.B. (2010). Single-machine scheduling with simple linear deterioration to minimize earliness penalties, International Journal of Advance Manufacturing Technology 46, 285–290.

Wang, J.B., Huang, X., Wang, X.Y., Yin, N., & Wang, L. (2009). Learning effect and deteriorating jobs in the single machine scheduling problems. Applied Mathematical Modeling, 33, 3848–3853.

Wu, C.C., Shiau, Y.R., Lee, L.H., & Lee, W.C. (2009). Scheduling deteriorating jobs to minimize the makespan on a single machine. International Journal of Advance Manufacturing Technology, 44, 1230–1236.

Yuan, J.J., Lin, X.Y., Cheng, T.C.E., & Ng, C.T. (2007). Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time. International Journal of Production Economics, 105, 402–406.

Yuan, J.J., Liu, Z.H., Ng, C.T., & Cheng, T.C.E. (2004). The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. Theoretical Computer Science, 320, 199–212.

Zhang,G., Cai, X., Lee, C.Y., & Wong, C.K. (2001). Minimizing makespan on a single batch processing machine with no identical job sizes. Naval Research Logistics, 48, 226–240.