A branch and bound algorithm to minimize the total weighted number of tardy jobs and delivery costs with late deliveries for a supply chain scheduling problem

Document Type : Research Paper

Authors

Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan 84156-83111, Iran

Abstract

In this paper, we study a supply chain scheduling problem that simultaneously considers production scheduling and product delivery.  jobs have to be scheduled on a single machine and delivered to  customers for further processing in batches. The objective is to minimize the sum of the total weighted number of tardy jobs and the delivery costs. In this paper, we present a heuristic algorithm (HA) and a branch and bound (B&B) method for the restricted case, where the tardy jobs are delivered separately, and compare these procedures with an existing dynamic programming (DP) algorithm by computational tests. The results of computational tests show significant improvement of the B&B over the dynamic programming algorithm.

Keywords

Main Subjects

References

Brucker P. and Kovalyov M.Y., 1996. Single Machine Batch Scheduling to Minimize The Weighted Number of Late Jobs, Mathematical Methods of Operation Research 43, 1-8.
Chen Z-L., 2010. Integrated Production and Outbound Distribution Scheduling: Review and Extensions. Operations Research 58 (1), 130-148.
Gens G.V. and Levner E.V., 1979. Discrete optimization problems and efficient approximate algorithms, Engineering Cybernetics 17 (6), 1-11.
Gens G.V. and Levner E.V., 1981. Fast Approximation Algorithm for Job Sequencing With Deadlines. Discrete Applied Mathematics 3 (4), 313-318.
Hall N.G., Potts C.N., 2003. Supply Chain Scheduling: Batching And Delivery. Operations Research 51 (4), 566-584.
Hallah R.M., Bulfin R.L., 2003. Minimizing the Weighted Number of Tardy Jobs on a Single Machine, European Journal of Operational Research 145, 45-56.
Hallah R.M., Bulfin R.L., 2007. Minimizing the Weighted Number of Tardy Jobs on a single machine with release dates, European Journal of Operational Research 176, 727-744.
Hamidinia A., Khakabimamaghani S., Mahdavi Mazdeh M., Jafari M., 2012, A genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system, Computers & Industrial Engineering 62, 29–38
Hochbaum D.S., Landy D., 1994. Scheduling with batching: minimizing the weighted number of tardy jobs. Operations Research Letters, 16:79-86.
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 745–755.
Kalantari, M., Rabbani, M. and Ebadian, M. (2011) ‘A decision support system for order acceptance/rejection in hybridMTS/MTO production systems’, Applied Mathematical Modelling, Vol. 35, No. 3, pp.1363–1377.
Karp, R. M., 1972. Reducibility among Combinatorial Problems. R. E. Miller, J. W. Thatcher, Eds. Complexity of Computer Computations. Plenum Press, New York, 85-103.
Mazdeh M.M., Sarhadi M., Ashouri A., Hindi K.S., 2011. Single-Machine Batch Scheduling Minimizing Weighted Flow Times and Delivery costs. Applied Mathematical Modelling 35, 563-570.
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, 74-86.
Mazdeh M.M., Sarhadi M., Hindi K.S., 2008. A Branch-And-Bound Algorithm For Single-Machine Scheduling With Batch Delivery And Job Release Times, Computers and Operations Research 35, 1099-1111.
Moore J. M., 1968. An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science 15, 102-109.
Rasti-Barzoki, M., & Hejazi, S. R. (2013). Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains. European Journal of Operational Research, 228, 345-357.
Rasti-Barzoki, M., & Hejazi, S. R. (2015). Pseudo-polynomial dynamic programming for an integrated due date assignment, resource allocation, production, and distribution scheduling model in supply chain scheduling. Applied Mathematical Modelling.
Rasti-Barzoki, M., Hejazi, S. R., & Mazdeh, M. M. (2013). A Branch and Bound Algorithm to Minimize the Total Weighed Number of Tardy Jobs and Delivery Costs. Applied Mathematical Modelling, 37, 4924-4937.
Ramayah, T., Roy, M.H., Li, K.B., Jantan, M., Zbib, I. and Ahmed, Z.U. (2007) ‘Type of  procurement and operational performance: comparing e-procurement and offline purchasing’.  International Journal of Services and Operations Management, Vol. 3, No. 3, pp.279–296.
Reisi–Nafchi, M., & Moslehi, G. (2015). Integrating two–agent scheduling and order acceptance problems to maximise total revenue by bounding each agent penalty function. International Journal of Services and Operations Management, 20, 358-384.
Renna, P. (2009) ‘A multi-agent system architecture for business-to-business applications’.  International Journal of Services and Operations Management, Vol. 5, No. 3, pp.375–401.  
Renna, P. (2012) ‘Simulation-based tool to analyse the effect oforder acceptance policy in a  make-to-order manufacturing system’, International Journal of Services and Operations  Management, Vol. 11, No. 1, pp.70–86.
Sahni S.K., 1976. Algorithms for Scheduling Independent Tasks. Journal of the ACM 23 (1), 116-127.
Steiner G., Zhang R., 2007. Minimizing the Weighted Number of Late Jobs with Batch Setup Times and Delivery costs on a Single Machine , Multiprocessor Scheduling: Theory and Applications, Book edited by Eugene Levner, Itech Education and Publishing, Vienna, Austria.
Steiner G., Zhang R., 2009. Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains, journal of scheduling 12, 565–574.
Yin, Y., Cheng, S.R., Cheng, T.C.E., Wu, W.H.and Wu, C.C. (2010) ‘Two-agent single-machine scheduling with release times and deadlines’. International Journal of Shipping and Transport Logistics, Vol. 5, No. 1, pp.75–94.
Zegordi S.H. Kamal Abadi I.N., Beheshti Nia, M.A., 2010. A novel genetic algorithm for solving production and transportation scheduling in a two-stage supply chain, Computers & Industrial Engineering 58, 373-381.

Files

History

  • Receive Date: 09 June 2016
  • Revise Date: 11 August 2016
  • Accept Date: 02 October 2016

Share

How to cite

Statistics