Optimization-based manufacturing scheduling with multiple resources, setup requirements, and transfer lots

Abstract

The increasing demand for on-time delivery of products and low production cost is forcing manufacturers to seek effective schedules to coordinate machines and operators so as to reduce costs associated with labor, setup, inventory, and unhappy customers. This paper presents the modeling and resolution of a job shop scheduling system for J. M. Products Inc., whose manufacturing is characterized by the need to simultaneously consider machines and operators, machines requiring significant setup times, operators of different capabilities, and lots dividable into transfer lots. These characteristics are typical for many manufacturers, difficult to handle, and have not been adequately addressed in the literature. In our study, an integer optimization formulation with a separable structure is developed where both machines and operators are modeled as resources with finite capacities. Setups are explicitly considered following our previous work with additional penalties on excessive setups. By analyzing transfer lot dynamics, transfer lots are modeled by using linear inequalities. The objective is to maximize on-time delivery of products, reduce inventory, and reduce the number of setups. By relaxing resource capacity constraints and portions of precedence constraints, the problem is decomposed into smaller subproblems that are effectively solved by using a novel dynamic programming procedure. The multipliers are updated using the recently developed surrogate subgradient method. A heuristic is then used to obtain a feasible schedule based on subproblem solutions. Numerical testing shows that the method generates high quality schedules in a timely fashion.