Sequence Dependent Scheduling Problems with Precedence Constraints

Byung-Chul Cha

Scheduling a single machine with arbitrary sequence dependent setup times with makespan objective is equivalent to the traveling salesman problem. Besides, the precedence relationship between jobs exists in many different SDSPs. In its most generic form, the single vehicle many-to-many Dial-A-Ride Problem (DARP) is the problem of minimizing the  tour traveled by a vehicle witch services N customers, each of whom wishes to go from a distinct origin to a distinct destination. The purpose of this paper is to develop several IP formulations and heuristic algorithms which can be applied to several different SDSPs with precedence constraints.