Analogies between flexible job shop scheduling and vehicle routing problems

Different similarities and analogies have been investigated between the travel salesman problem (TSP) and the one machine sequencing problem, and common heuristics and bounds were also established for both of them. Recently, works focalized on possible analogies between variants of vehicle routing problems (VRP) and parallel machine scheduling problems in Beck, J-C, et al., (2003). In this paper, we present different analogies between two complex combinatorial optimization problems: the VRP and the flexible job shop scheduling problem (FJSSP) and use it for the calculation of new VRP lower bounds in Carlier, J. et al., (1988).