Volume 3 Issue 3 pp. 347-364 Spring, 2012


Single-machine batch scheduling minimizing weighted flow times and delivery costs with job release times


Mohammad Mahdavi Mazdeh, Ali Naji Esfahani, Seyyed Ershad Sakkaki and Amir Ebrahimzadeh Pilerood


This paper addresses scheduling a set of weighted jobs on a single machine in presence of release date for delivery in batches to customers or to other machines for further processing. The problem is a natural extension of minimizing the sum of weighted flow times by considering the possibility of delivering jobs in batches and introducing batch delivery costs. The classical problem is NP-hard and then the extended version of the problem is NP-hard. The objective function is that of minimizing the sum of weighted flow times and delivery costs. The extended problem arises in a real supply chain network by cooperation between two layers of chain. Structural properties of the problem are investigated and used to devise a branch-and-bound solution scheme. Computational experiments show the efficiency of suggested algorithm for solving instances up to 40 jobs.


DOI: 10.5267/j.ijiec.2012.01.004

Keywords: Scheduling, Single machine, Batch delivery, Branch and bound, Weighted flowtimes

References

References Baker KR. (1974). Introduction to Sequencing and Scheduling. Wiley, NewYork, Wiley.

Belouadah, H., Posner, M.E., & Potts, C.N. (1992). Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Applied Mathematics, 36(3), 213-231.

Bianco, L. & Ricciardelli, S. (1982). Scheduling of a single machine to minimize total weighted completion time subject to release dates. Naval Research Logistics Quarterly, 29(1), 151-167.

Chandra, R. (1979). On n/1/F¦ dynamic deterministic problems. Naval Research Logistics Quarterly, 26(3), 537-544.

Chou, C.F.M. (2004). Asymptotic performance ratio of an online algorithm for the single machine scheduling with release dates. IEEE Transactions on Automatic Control, 49(5), 772-776.

Chu,C. (1992). A branch-and-bound algorithm to minimize total flow time with unequal release dates. Naval Research Logistics (NRL), 39(6), 859-875.

Dessouky, M. I. & Deogun, J. S. (1981). Sequencing Jobs with Unequal Ready Times to Minimize Mean Flow Time. SIAM Journal on Computing, 10(1), 192-202.

Graham, R.L., Lawler, E.L., Lenstra, J.K., & Kan, A.H.G.R. (1979). Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. InP.L.Hammer (Ed.), Annals of Discrete Mathematics Discrete Optimization II, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium co-sponsored by IBM Canada and SIAM Banff, Aha. and Vancouver (287-326). Elsevier.

Hall, N. & Potts, C.N. (2003). Supply chain scheduling: batching and delivery. Operations Research, 51, 566-584.

Hariri, A.M.A. & Potts, C.N. (1983). An algorithm for single machine sequencing with release dates to minimize total weighted completion time. Discrete Applied Mathematics, 5(1), 99-109.

Ji,M., He,Y., & Cheng, T.C.E. (2007). Batch delivery scheduling with batch delivery cost on a single machine. European Journal of Operational Research, 176(2), 745-755.

Kahlbacher,H.G. & Cheng,T.C.E. (1993). Parallel machine scheduling to minimize costs for earliness and number of tardy jobs. Discrete Applied Mathematics, 47(2), 139-164.

Labetoulle, J, Lawler, Eugene L., Lenstra, J. K., and Rinnooy Kan, A. H. G. (1984). Preemptive scheduling of uniform machines subject to release dates. Stichting Mathematisch Centrum, 245-261.

Lenstra, J.K., Rinnooy Kan, A.H.G., & Brucker,P. (1977). Complexity of Machine Scheduling Problems. InP.L.Hammer (Ed.), Annals of Discrete Mathematics Studies in Integer Programming, 343-362.

Mahdavi Mazdeh, M., Sarhadi, M., & Hindi, K.S. (2008). A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times. Computers & Operations Research, 35(4), 1099-1111.

Mazdeh, M.M., Sarhadi, M., & Hindi, K.S. (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(1), 74-86.

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

Smith,W.E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1-2), 59-66.