Scheduling job shops with transfer lots

For the production of mid to high volume products with long setups, products are generally grouped into production lots. Previously, lot splitting techniques were used to split a lot into multiple smaller transfer lots, and each transfer lot can be transferred to its successor operation immediately upon completion. This paper presents a novel integer programming formulation for scheduling job shops with transfer lots without introducing excessive decision variables relating to transfer lots. A combined Lagrangian relaxation and dynamic programming algorithm is used to solved the problem. After coupling constraints are relaxed by using Lagrange multipliers, the problem is decomposed into lot-level subproblems, and an efficient dynamic programming algorithm is developed to solve these subproblems. The multipliers are updated at the high level by using the previously developed reduced complexity bundle method. Numerical testing results show that the algorithm can be effectively used to schedule job shops with transfer lots