Cyclic machine scheduling with tool transportation

摘要

This thesis concerns a cyclic machine scheduling problem with characteristic feature that also tools have to be transported. We speak about a machine scheduling problem, because it deals with the question how to make optimal use of a set of machines for the processing of a set of tasks. It is a cyclic scheduling problem because the objective is to find a schedule that does not have a real starting or finishing point, but that can be continuously repeated. An example of a cyclic schedule is, e.g., the time table that can be found at a Dutch train station. This time table is a cyclic schedule that is repeated every hour. For the processing of tasks, machines frequently need certain tools. These tools may be very expensive. If this is the case, then it can be lucrative that the machines share the tools. This, however, has the consequence that the tools have to be transported between the machines. This can, e.g, be done by a person, a conveyer belt or a robot. In the problem that is considered in this thesis, a robot is used. This robot can only transport one tool at a time. Depending on the velocity of the robot and the times that the machines need to process the tasks, the processing times of the tasks, it may happen that a machine cannot start with a next task, because the required tool has not arrived yet at that machine. This implies that the machine becomes idle for some time. This, obviously, is not very efficient. In general, one will try to keep the machines busy as much as possible, in order to maximize the average production per unit of time. In this thesis, we try to answer the question with what cyclic schedule, given the velocity of the robot and the processing times of the tasks, the average production per unit of time can be maximized.