This article treats a scheduling problem where timely departures of vehicles executing Just-In-Time (JIT) deliveries between a single supplier and a single receiver along with the assignment of supplies to vehicles are to be determined. This problem, for instance, arises in the automotive industry where parts are to be delivered JIT from a central distribution center to a car manufacturer. We define different subproblems and provide an analysis of computational complexity along with suitable solution procedures. Furthermore, we apply these procedures to an industry case, so that managerial implications are revealed; e.g., with regard to the impact of standardized containers on delivery costs.