Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and set-up times using the Travelling Salesman Problem with time windows

Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and set-up times using the Travelling Salesman Problem with time windows

0.00 Avg rating0 Votes
Article ID: iaor19991754
Country: Netherlands
Volume: 100
Issue: 3
Start Page Number: 494
End Page Number: 513
Publication Date: Aug 1997
Journal: European Journal of Operational Research
Authors: , , , ,
Keywords: programming: travelling salesman, programming: dynamic
Abstract:

In this paper we consider the Discrete Lotsizing and Scheduling Problem with sequence dependent set-up costs and set-up times (DLSPSD). DLSPSD contains elements from lotsizing and from job scheduling, and is known to be NP-Hard. An exact solution procedure for DLSPSD is developed, based on a transformation of DLSPSD into a Travelling Salesman Problem with Time Windows (TSPTW). TSPTW is solved by a novel dynamic programming approach due to Dumas et al. The results of a computational study show that the algorithm is the first one capable of solving DLSPSD problems of moderate size to optimality with a reasonable computational effort.

Reviews

Required fields are marked *. Your email address will not be published.