Two-stage production scheduling with an option of outsourcing from a remote supplier

Abstract

This paper studies a two-stage production system with n job orders where each job needs two sequential operations. In addition to the two in-house production facilities, the manufacturer has another option of outsourcing some stage-one operations to a remote outside supplier. The jobs with their stage-one operations outsourced are subject to a batch transportation delay from the outside supplier before their respective stage-two operations can be started in-house. The problem is to design an integrated schedule that considers both the in-house production and the outsourcing with the aim of optimally balancing the outsourcing cost and the makespan. The problem is NP-hard. We have developed an optimal algorithm and a heuristic algorithm to solve the problem, and conducted computational experiments to validate our model and algorithms. Our modeling and algorithm framework can be extended to handle other more general cases such as when the outside supplier has a production facility with a different processing efficiency and when there are many outside suppliers on a spot market.

Keywords

Outsourcing / scheduling / algorithms

References

[1] Agnetis A., Hall N.G., Pacciarelli D.. Supply chain scheduling: sequence coordination. Discrete Applied Mathematics, 2006, 154: 2044-2063.

[2] Aydinliyim, T. & Vairaktarakis, G.L. (2006). Coordination of outsourcing operations. Working paper

[3] Cai X., Lee C.Y., Vairaktarakis G.L.. Optimization of processing and delivery decisions involving third-party machines. Nonlinear Analysis, 2005, 63: 2269-2278.

[4] Chang Y.C., Lee C.Y.. Machine scheduling with job delivery coordination. European Journal of Operational Research, 2004, 158: 470-487.

[5] Chen Z.L., Li C.L.. Scheduling with subcontracting options. IIE Transactions, 2008, 40: 1171-1184.

[6] Chen Z.L., Pundoor G.. Order assignment and scheduling in a supply chain. Operations Research, 2006, 54: 555-572.

[7] Chen Z.L., Vairaktarakis G.L.. Integrated scheduling of production and distribution operations. Management Science, 2005, 51: 614-628.

[8] Cheng T.C.E., Kovalyov M.Y.. Single supplier scheduling for multiple deliveries. Annals of Operations Research, 2001, 107: 51-63.

[9] Chung D., Lee K., Shin K., Park J.. A new approach to job shop scheduling problems with due date constraints considering operation subcontracts. International Journal of Production Economics, 2005, 98: 238-250.

[10] Dawande M., Geismar H.N., Hall N.G., Sriskandarajah C.. Supply chain scheduling: distribution systems. Production and Operations Management, 2006, 15: 243-261.

[11] Hall N.G., Potts C.N.. Supply chain scheduling: batching and delivery. Operations Research, 2003, 51: 566-584.

[12] Hall N.G., Potts C.N.. The coordination of scheduling and batch deliveries. Annals of Operations Research, 2005, 135: 41-64.

[13] Kreipl S., Pinedo M.. Planning and scheduling in supply chains: an overview of issues in practice. Production and Operations Management, 2004, 13: 77-92.

[14] Kyparisis G.J., Koulamas C.. A note on makespan minimization in two-stage flexible flow shops with uniform machines. European Journal of Operational Research, 2006, 175: 1321-1327.

[15] Lee C.Y., Vairaktarakis G.L.. Minimizing makespan in hybrid flowshops. Operations Research Letters, 1994, 16: 149-158.

[16] Lee C.Y., Chen Z.L.. Machine scheduling with transportation considerations. Journal of Scheduling, 2001, 4: 3-24.

[17] Lee C.Y., Leung J.Y.T., Yu G.. Two machine scheduling under disruptions with transportation considerations. Journal of Scheduling, 2006, 9: 35-48.

[18] Lee I.S., Sung C.S.. Minimizing due date related measures for a single machine scheduling problem with outsourcing allowed. European Journal of Operational Research, 2008, 186: 931-952.

[19] Lee I.S., Sung C.S.. Single machine scheduling with outsourcing allowed. International Journal of Production Economics, 2008, 101: 623-634.

[20] Lee Y.H., Jeong C.S., Moon C.. Advanced planning and scheduling with outsourcing in manufacturing supply chain. Computers and Industrial Engineering, 2002, 43: 351-374.

[21] Lenstra J.K., Rinnooy Kan A.H.G., Brucker P.. Complexity of machine scheduling problems. Annuals of Discrete Mathematics, 1977, 1: 343-362.

[22] Li C.L., Xiao W.Q.. Lot streaming with supplier-manufacturer coordination. Naval Research Logistics, 2004, 51: 522-542.

[23] Li C.L., Vairaktarakis G.L., Lee C.Y.. Machine scheduling with deliveries to two customer locations. European Journal of Operational Research, 2005, 164: 39-51.

[24] Oguz C., Ercan M.. A genetic algorithm for hybrid flow-shop scheduling ith multiprocessor tasks. Journal of Scheduling, 2005, 8: 323-351.

[25] Qi X.. A logistics scheduling model: inventory cost reduction by batching. Naval Research Logistics, 2005, 52: 312-320.

[26] Qi X.. A logistics scheduling model: scheduling and transshipment for two processing centers. IIE Transactions, 2006, 38: 609-618.

[27] Qi X.. Coordinated logistics scheduling for in-house production and outsourcing. IEEE Transactions on Automation Science and Engineering, 2008, 5: 188-192.

[28] Ruiz-Torres A.J., Ho J.C., Lopez F.J.. Generating Pareto schedules with outsource and internal parallel resources. International Journal of Production Economics, 2006, 103: 810-825.

[29] Sundararaghavan P.S., Kunnathur A.S., Viswanathan I.. Minimizing makespan in parallel flowshops. Journal of the Operational Research Society, 1997, 48: 834-842.

[30] Tang L., Xuan H., Liu J.. A new Lagrangian relaxation algorithm for hybrid lowshop scheduling to minimize total weighted completion time. Computers & Operations Research, 2006, 33: 3344-3359.

[31] Vairaktarakis, G.L. (2006a). Non-cooperative outsourcing games. Working paper

[32] Vairaktarakis, G.L. (2006b). Cooperative strategies for manufacturing planning with negotiable third-party capacity. Working paper.

[33] Wang H., Lee C.Y.. Production and transport logistics scheduling with two transport mode choices. Naval Research Logistics, 2005, 52: 796-809.