演講者：Prof. Shunji Tanaka田中俊二教授
Department of Electrical Engineering, Institute for Liberal Arts and Sciences
Title: Exact Algorithms for Single-machine Scheduling Problems
Abstract: The machine scheduling problem is one of the most widely studied combinatorial optimization problems. This problem is NP-hard in general even if only a single machine is considered. However, recent advances in scheduling theory have enabled us to solve this kind of problem to optimality quite efficiently. In this talk, I will introduce our exact algorithm for the general single-machine scheduling problem to minimize total job completion cost. I will also explain its extensions to several types of single-machine scheduling problem.
Title: Exact Algorithms for Container Relocation and Pre-marshalling Problems
Abstract: In this talk, mainly two problems arising in container terminals are considered. The container relocation problem, which is also known as the block relocation problem, aims at minimizing the number of relocations necessary for retrieving all containers stacked vertically one by one. On the other hand, the container pre-marshalling problem does not retrieve any containers but just rearrange them with the minimum number of relocations so that we can retrieve them easily in the future. In this talk, I first review these problems as well as relevant problems, and then introduce our exact algorithms for them.