Single Machine Scheduling Problem with Batch Outsourcing

Document Type : Original Article

Authors

Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

Abstract

Outsourcing as a useful strategy in the industry can be integrated into scheduling problems. Moreover, batch outsourcing is a practical assumption owing to the logistics issues for transferring the parts between the manufacturer and the subcontractors. However, this assumption is rarely addressed in the scheduling literature. In this paper, a novel single machine scheduling problem with the option of batch outsourcing is studied. The objective is to minimize the sum of the total completion time of the jobs and the total outsourcing cost. To solve the problem, first, two mixed-integer linear programming (MILP) models, named MP1 and MP2, are developed, which respectively use a straightforward and an innovative approach to model the outsourcing batches. Next, an optimal property for the outsourcing batches is proven. This property is used to establish a valid inequality for model MP2, which is added to it to obtain a third MILP model, MP3. Extensive computational experiments showed that MP2 outperforms MP1 significantly. Moreover, including the derived valid inequality in MP3 enhances its performance considerably in comparing to MP2. Furthermore, it is observed that MP3 is capable of solving many practical-size problem instances optimally or with a low maximum optimality gap.

Keywords

Main Subjects

References

  1. Fakhrzad M.B., "Outsourcing through Three-dimensional Competition." International Journal of Engineering, Transactions C: Aspects, Vol. 27, No. 12, (2014), 1863-1871. DOI: 10.5829/idosi.ije.2014.27.12c.09
  2. Enayati M., Asadi-Gangraj E. and Paydar M.M., "Scheduling on flexible flow shop with cost-related objective function considering outsourcing options." Journal of Optimization in Industrial Engineering, Vol. 14, No. 2, (2021), 53-72. DOI: 10.22094/joie.2020.1873983.1674.
  3. Wang and Cui W., "Approximation algorithms for the min-max regret identical parallel machine scheduling problem with outsourcing and uncertain processing time." International Journal of Production Research, Vol. 59, No. 15, (2020), 4579-4592. DOI: 10.1080/00207543.2020.1766721.
  4. Gholamian K., Vakilifard H., Talebnia G. and Hejazi R., "Conceptual design of sustainable outsourcing with balanced scorecard using analytic hierarchy process: a case study for Fajr Jam gas refining company." International Journal of Engineering, Transactions A: Basics, Vol. 33, 1, (2020), 112-123. DOI:10.5829/ije.2020.33.01a.13.
  5. Jiang X., Zhang A., Chen Y., Chen G. and Lee K., "An improved algorithm for a two-stage production scheduling problem with an outsourcing option." Theoretical Computer Science, Vol. 876, (2021), 59-69. DOI: 10.1016/j.tcs.2021.05.022.
  6. Zhong X., Fan J. and Ou J., "Coordinated scheduling of the outsourcing, in-house production and distribution operations." European Journal of Operational Research, In Press, (2022). DOI: 10.1016/j.ejor.2022.01.003.
  7. Aksen D., Şengül Akca S. and Aras N., "A bi-level partial interdiction problem with capacitated facilities and demand outsourcing." Computers & Operations Research, Vol. 41, (2014), 346-358. DOI: 10.1016/j.cor.2012.08.013.
  8. Alizadeh M., Mahdavi I., Shiripour S. and Asadi H., "A non-linear model for a capacitated location-allocation problem with Bernoulli demand using sub-sources." International Journal of Engineering, Transactions C: Aspects, Vol. 26, No. 9, (2013), 1007-1016. DOI: 10.5829/idosi.ije.2013.26.09c.08.
  9. Mehdizadeh E. and Fatehi Kivi A., "Three meta-heuristic algorithms for the single-item capacitated lot-sizing problem." International Journal of Engineering, Transactions, B: Applications Vol. 27, No. 8, (2014), 1223-1232. DOI: 10.5829/idosi.ije.2014.27.08b.08.
  10. Parvasi S.P., Mahmoodjanloo M. and Setak M., "A bi-level school bus routing problem with bus stops selection and possibility of demand outsourcing." Applied Soft Computing, Vol. 61, (2017), 222-238. DOI: 10.1016/j.asoc.2017.08.018.
  11. Giri B.C. and Sarker B.R., "Improving performance by coordinating a supply chain with third party logistics outsourcing under production disruption." Computers & Industrial Engineering, Vol. 103, (2017), 168-177. DOI: 10.1016/j.cie.2016.11.022.
  12. Kim B., Park K.S., Jung S.Y. and Park S.H., "Offshoring and outsourcing in a global supply chain: Impact of the arm’s length regulation on transfer pricing." European Journal of Operational Research, Vol. 266, No. 1, (2018), 88-98. DOI: 10.1016/j.ejor.2017.09.004.
  13. Heydari J., Govindan K., Ebrahimi Nasab H.R. and Taleizadeh A.A., "Coordination by quantity flexibility contract in a two-echelon supply chain system: Effect of outsourcing decisions." International Journal of Production Economics, Vol. 225, (2020), 107586. DOI: 10.1016/j.ijpe.2019.107586.
  14. Fathollahi-Fard A.M., Hajiaghaei Keshteli M., Tavakkoli Moghaddam R. and Smith N.R., "Bi-level programming for home health care supply chain considering outsourcing." Journal of Industrial Information Integration, Vol. 25, (2022), 100246. DOI: 10.1016/j.jii.2021.100246.
  15. Baker K.R. and Trietsch D., Principles of Sequencing and Scheduling. 1st edition. Hoboken, N.J: Wiley, 2009.
  16. Safarzadeh H. and Kianfar F., "Job shop scheduling with the option of jobs outsourcing." International Journal of Production Research, Vol. 57, Vol. 10, (2019), 3255-3272. DOI: 10.1080/00207543.2019.1579934.
  17. Pinedo M.L., Scheduling: Theory, Algorithms, and Systems. Springer Science & Business Media, 2012.
  18. Liu L., "Outsourcing and rescheduling for a two-machine flow shop with the disruption of new arriving jobs: A hybrid variable neighborhood search algorithm." Computers & Industrial Engineering, Vol. 130, (2019), 198-221. DOI: 10.1016/j.cie.2019.02.015.
  19. Qi X., "Coordinated Logistics Scheduling for In-House Production and Outsourcing." IEEE Transactions on Automation Science and Engineering, Vol. 5, No. 1, (2008), 188-192. DOI: 10.1109/TASE.2006.887159.
  20. Qi X., "Two-stage production scheduling with an option of outsourcing from a remote supplier." Journal of Systems Science and Systems Engineering, Vol. 18, No. 1, (2009), 1-15. DOI: 10.1007/s11518-009-5094-1.
  21. Qi X., "Outsourcing and production scheduling for a two-stage flow shop." International Journal of Production Economics, Vol. 129, No. 1, (2011), 43-50. DOI: 10.1016/j.ijpe.2010.08.011.
  22. Ahmadizar F. and Amiri Z., "Outsourcing and scheduling for a two-machine flow shop with release times." Engineering Optimization, Vol. 50, No. 3, (2018), 483-498. DOI: 10.1080/0305215X.2017.1325483.
  23. Lee I.S. and Sung C.S., "Minimizing due date related measures for a single machine scheduling problem with outsourcing allowed." European Journal of Operational Research, Vol. 186, No. 3, (2008), 931-952. DOI: 10.1016/j.ejor.2007.02.015.
  24. Lee I.S. and Sung C.S., "Single machine scheduling with outsourcing allowed." International Journal of Production Economics, Vol. 111, No. 2, (2008), 623-634. DOI: 10.1016/j.ijpe.2007.02.036.
  25. Zhong W. and Huo Z., "Single machine scheduling problems with subcontracting options." Journal of Combinatorial Optimization, Vol. 26, No. 3, (2013), 489-498. DOI: 10.1007/s10878-011-9442-y.
  26. Hong J.M. and Lee J.H., "Outsourcing decisions in single machine scheduling problem with multiple external facilities." Journal of Marine Science and Technology, Vol. 24, No. 3, (2016), 603-609. DOI: 10.6119/JMST-015-1216-1.
  27. Ren J., Sun G. and Zhang Y., "The Supplying Chain Scheduling with Outsourcing and Transportation." Asia-Pacific Journal of Operational Research, Vol. 34, No, 02, (2017), DOI: 10.1142/S0217595917500099.
  28. Chen Z.L. and Li C.L., "Scheduling with subcontracting options." IIE Transactions, Vol. 40, No. 12, (2008), 1171-1184. DOI: 10.1080/07408170801975057.
  29. Guo X. and Lei D., "Bi-objective job shop scheduling with outsourcing options." International Journal of Production Research, Vol. 52, No. 13, (2014), 3832-3841. DOI: 10.1080/00207543.2013.848488.
  30. Izadi L., Ahmadizar F. and Arkat J., "A Hybrid Genetic Algorithm for Integrated Production and Distribution Scheduling Problem with Outsourcing Allowed." International Journal of Engineering, Transactions B: Applications, Vol. 33, No. 11, (2020), 2285-2298. DOI: 10.5829/ije.2020.33.11b.19.
  31. Ku W.Y. and Beck J.C., "Mixed Integer Programming models for job shop scheduling: A computational analysis." Computers & Operations Research, Vol. 73, Supplement C, (2016), 165-173. DOI: 10.1016/j.cor.2016.04.006.
  32. Ham A.M. and Cakici E., "Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches." Computers & Industrial Engineering, Vol. 102, Supplement C, (2016), 160-165. DOI: 10.1016/j.cie.2016.11.001.
  33. Meng L., Zhang C., Shao X., Zhang B., Ren Y. and Lin W., "More MILP models for hybrid flow shop scheduling problem and its extended problems." International Journal of Production Research, (2019), 1-26. DOI: 10.1080/00207543.2019.1636324.
International Journal of Engineering
Volume 35, Issue 5
TRANSACTIONS B: Applications
May 2022
Pages 1006-1016

Files

Cited by

Share

How to cite

Statistics