The research objectives of this award are the design and the development of new algorithmic structures that will improve on the planning and scheduling of the transport of goods in global supply chains. The research approach will focus on the interface between two research directions that in recent years have received, separately, an enormous amount of attention; namely research that has been done on scheduling problems and research that has been done on packing problems (including knapsack problems and bin-packing problems). A focus on problem classes with scheduling aspects as well as packing aspects is highly relevant since all major modes of transportation (e.g., container ships, trucks, etc.) have a finite capacity.
If successful, this research will yield new algorithmic structures and heuristics that will result in a more efficient movement of goods, i.e., transportation at a lower cost and more timely. The principal investigators of this research project collaborate closely with supply chain managers in industry. More efficient management of the supply chains may lead to a total transportation cost reduction of 1-2 percent and may lead to improvements in on-time deliveries as well. Graduate students will benefit through classroom instruction and involvement with the research.
In this project we have focused on more "modern" scheduling problems which have important applications in the real world. The real world applications occur in many different environments: not only in container shipment scheduling, but also, for example, in health care applications such as operating room scheduling. Before analyzing the real applications in depth, we do look at related more general (and more stylized) classical scheduling models, including single machine, parallel machines and flow shop scheduling problems. Results for single machine and parallel machine scheduling problems are of importance for container shipment scheduling as well as operating theatre scheduling. (A machine in a parallel machine environment may represent a container ship or an operating room.) In addition, we are adding new features to our scheduling problems, which have not been analyzed in depth yet in the literature. These features include multiple objective functions, machine eligibility constraints, coordination mechanisms, and online versions of our problems. All the features considered are of importance in real life scheduling applications, whether it is container scheduling or health-care scheduling. The results we obtained fit within a fairly common framework: We first try to establish which versions of our scheduling problems can be solved efficiently (i.e., can be solved in polynomial time) and which versions do not admit an efficient algorithm (i.e., they are either weakly or strongly NP-hard). For those versions that do not admit efficient algorithms, we develop efficient heuristics and approximation schemes and analyze their performance either through computational studies or through mathematical analysis.
