The changeover scheduling problem with time and cost considerations: Analytical results and a forward algorithm

In a multiproduct, discrete-item manufacturing environment, it is often mor e economical to have one "flexible" machine to produce several products rat her than to have a dedicated machine for the production of each product. We consider the problem of scheduling multiple products on a single-finite-ca pacity resource when faced with product-dependent, but sequence-independent , changeover costs and times. The problem horizon is assumed finite and the demand time-varying and known over this horizon. The objective is to find a feasible schedule that meets all demand on time and minimizes the total c hangeover cost. With the "delivery-on-time-or-else" mentality and the trend toward shorter order-to-delivery lead times, scheduling and managing changeovers has becom e just that much more important. We first present analytical results to red uce the feasible solution space and then develop a branch-and-bound algorit hm to solve this NP-complete problem. Computational results are presented t hat show that the algorithm can solve realistic size problems in a reasonab le amount of time.