Solution Algorithms for Three-machine Flowshop Scheduling to Minimize the Total Weighted Completion Times with Outsourcing Lead-time

This paper examines a scheduling problem in a three-machine flowshop considering outsourcing lead-time. In this problem, the initial or second operations of jobs can be processed either internally or by external subcontractors, while the third operation is required to be completed internally. Outsourcing incurs specific costs related to each operation and a lead time, which means that subsequent operations can only begin after this lead time has passed. The objective of this study is to minimize the sum of both the outsourcing costs and the total weighted completion times. Two outsourcing priority rules and three processing priority rules were proposed, leading to the development of six heuristic algorithm combinations. This research also identified several solution properties, derived a problem-specific lower bound, and introduced a branch-and-bound algorithm. Computational experiments indicate that these proposed algorithms provide both efficient and effective solutions. Future research could focus on expanding the diversity of outsourcing options. Discount rates based on the number of outsourced tasks could be incorporated into the total cost calculation, or outsourcing lead time negotiations could be treated as a variable. Additionally, factors such as the production capacity of subcontractors and delivery distances could be considered, with potential extensions to multi-machine environments.