AN IMPROVED ALGORITHM FOR THE MACHINE SCHEDULING PROBLEM WITH JOB DELIVERY COORDINATION

A two-stage supply chain scheduling problem is considered, where the first stage is job production and the second stage is job delivery. The focus is on the study of the integration of production scheduling with delivery of finished products to customers. In our considered model each job can be processed on either of two identical machines, and then delivered by a vehicle to a customer location. We present an improved algorithm with the worst-case performance ratio 14/9 + ɛ, which improves the known upper bounds of 2 and 5/3 in [Chang, Y.C. and Lee, C.Y., E. J. O. R., 158 (2004), pp. 470-487; Zhong, W., Dosa, G. and Tan, Z.Y., E. J. O. R., 182(2007), pp. 1057-1072].