ALPHABOT was developed to illustrate our research on the scheduling problem called the blocking job shop with rail-bound transportation BJS-RT. See my publications for further details.

ALPHABOT resembles a flexible manufacturing system. It consists of five machines and a transportation system with three robots. The jobs are processed on the machines and are transported from one machine to the next by the robots that move on a single rail line. The robots cannot pass each other, must maintain a minimum distance from each other, but can move out of the way.

A feature of the system is the absence of buffers, that means there is no storage space in the system. Hence, a job - once started and until its completion - is either on a machine or on a robot. After completing a machining operation, a job might wait on the machine – in effect blocking it – until it is picked up by a robot. Similarly, after completing a transport operation, a job must wait on the robot until being handed over to the machine for the next operation.

The picture on the right (click on it to enlarge) shows a production system with five machines and three robots. The complete system was build using Lego Mindstorm NXT Kits. A special thanks to Thierry Messer, Marc Wiedmer, Eemeli Rantakeisu and Cedric Lothritz for their excellent work on this project.

ALPHABOT constructs words. The raw material are dices. Each dice has a single letter on its faces. Each machine has four stacks of dices, and there is just one kind of dice (one letter) in a stack. A job consists in constructing a specified word by collecting the dices in the correct order. A small container is used to hold the dices.

The picture on the right (click on it to enlarge) shows a machine containing the letters I,J,K and L. It is holding the container of the job "ALPAHBOT".

Given a set of words, the goal is to produce these words as fast as possible. A schedule is obtained by modeling this task as an instance of the BJS-RT (see my publications). Our computational framework determines an optimized schedule. This schedule is sent to the ALPHABOT control software, which is responsible for the execution.

In this example, we use two robots and four machines. The layout looks as follows:

The task consists in constructing the three (nonsense) words “EFJKADN”, “ONMJHAC” and “BCEFBMNO”. The optimized schedule looks as follows: The horizontal axis depicts the time and the vertical axis the position on the x-axis (the rail).

The execution of this example can be seen in the following video:

In order to illustrate the impact of scheduling, we present a larger example with two robots, five machines and 18 words. The layout looks as follows:

The following 18 names are built: Heinz, Marino, Tony, Ivo, Reinhard, Francesca, Christoph, Sebastian, Thierry, Marc, Eemeli, Cedric, Antoine, Andreas, Claudine, Ophelie, Pham, Andreas.

A simple schedule is obtained by constructing one name after another. This is a so called job permutation schedule. The following figure depicts such a schedule in a Gantt chart: (The trajectories of the robots are not shown.) The horizontal and vertical axis depicts the time and the processors (machines and robots), respectively. Each bar represents a specific operational step (take-over, processing, transportation, hand-over). Thin bars represent waiting times of a job on a machine or a robot and hatched bars represent idle moves of the robots. Additionally, each job is illustrated below the main Gantt chart. In this schedule, 2250 seconds are used to build the names.

The following figure depicts an optimized schedule obtained with our optimization framework: In this schedule, 1336 seconds are used to build the names, which is an improvement of about 40% compared to the job permutation schedule seen before.