S.O.S - Scheduling Open Shop

Objectives:

The issue of sustainable mobility in large cities has increasingly gained attention in the later years. In turn this includes many other topics such as public transport, alternative transportation means, low-emission vehicles, and so forth.

A topic that has not received proper attention is the mobilization of cargo vehicles throughout the city. Cargo vehicles such as trucks, buses and vans, in addition of having a greater size than the average private passenger vehicles, move at lower speeds than the other vehicles in the cities. Moreover, the locations where these vehicles operate are characterized by a high density of businesses and warehouses, and by heavy traffic. These vehicles, when arrive to their destinations, usually wait for loading/unloading for long periods of time causing congestion and loss of productivity. These problems have increased with the arrival of hypermarkets, located in residential areas.

The problem of routing and scheduling trucks through warehouses has been widely studied. One may infer that there are two agents (trucks and warehouses) and therefore two points of view for the same problem: The trucks' view and the warehouses' view. These two agents can have conflicting objectives and a schedule that is adequate for one agent may be infeasible for the other one.

From the standpoint of the trucks, the routing has typically been defined as a classical Vehicle Routing Problem with Time Window constraints (VRPTW). In the classic sense, this approach does not consider the problem of capacity of loading and unloading of the warehouse. In other words, the VRPTW approach always assume that the warehouse is ready to serve the truck as long as it arrives during a pre-established time window. In practice, trucks do wait at warehouses because there are loading/unloading constraints.

Warehouses themselves have their own objectives and they do schedule the arrival of trucks. This schedule imposes constraints to the arrivals of trucks which in practice are viewed as time windows by the trucks. In this way, warehouses attempt to mitigate the truck waiting times.

The truck routing and warehouse scheduling problems may be solved separately and the resulting schedules can be satisfactory for both agents. However, as the problem scales up to multiple warehouses and trucks, the resulting schedules may be either infeasible or inadequate for one or more agents. What it is needed is an integrated approach that provides global optimization algorithms.

This combined routing and scheduling problem, according to the scheduling notation, can be defined as an Open Shop with Sequence Dependent Setup Times: In an Open Shop, all jobs (trucks) can visit the machines (warehouses) in the order they wish. Therefore the truck routes have to be established. Likewise, the order in which each warehouse sequences its trucks has to be also defined. The Sequence Dependent Setup Times are one constraint that refer to the fact that trucks must travel between warehouses and the travel times are modeled as setup times.

The purpose of this project is to provide a mechanism to solve the mentioned routing and (open shop) scheduling problems in the context of mobility of cargo vehicles. Specifically, we aim at creating an environment in which the scheduling expert is able to:

• Model most (open shop) scheduling problem and their constraints for real life settings.
• Use, at low cost, diverse algorithms to solve the problem
• Compare the results to be able to choose the one that provides the best performance in terms of solution quality and computer time. It should also be scalable, flexible and efficient.
• Explain the results in terms of the domain of the initial problem.