HomePage of Philippe Lacomme

Philippe Lacomme

Depuis 1999, je suis enseignant-chercheur. Mes activités de recherche soint orientées principalement autour des problèmes de tournées et d'ordonnancement.

Job-Shop with one single robot

Instances for the

Job-Shop with one single robot and buffer facilities
Problem definition :
  •   a finite set of n jobs;
  • each job consists of a sequence of operations
  • a set of m machines with infinite buffer capacity;
  • each machine can process at most one operation at a time;
  • each operation required to be processed during an uninterrupted period of a fixed duration.
  • each machine has one input buffer with limited capacity;
  • each machine has one output buffer with limited capacity;
  • a single transport robot is available;
  • each job transfer from any machine output buffer to any machine input buffer requires the transport robot;
  • the input buffer management rule is FIFO (First In First Out);
  • the output buffers management rule is FIFO;
  • one job can block a machine for a duration greater or equal to its processing time specified in its type if the output buffer is full;
  • to avoid deadlock, the maximal number of jobs is limited in the system;
  • no empty trip can start before one job reaches the front of output buffer of the machine (no-move ahead constraints);
Example of problem and of one solution:
Input buffer capacity = 2 (for all machines)

Output buffer capacity = 2 (for all machines)

Loaded time=unloaded time = 1

The maximal nomber of job in the system = 2

Type of job:
job 1: M1(0), M2(8), M3(16), M5(12), M6(0)
job 2: M1(0), M2(20), M4(10), M3(18), M6(0)
job 3: M1(0), M4(12), M5(8), M2(15), M6(0)		 Transportation time matrix for both loaded and empty trips:

matric
First MILP formulation provided by [2].
First representation :
s
Second representation :
solution
Instances: download
Instances format :                                                      
Remark : both loaded transportation time and empty transportation time are assumed to be identical
Best known solutions:

t
t
References:

[1]  Lacomme P., Moukrim A. and Tchernev N., “Simultaneously Job Input Sequencing and Vehicle Dispatching in a Single Vehicle AGVS: a Heuristic Branch and Bound Approach Coupled with a Discrete Events Simulation Model”, International Journal of Production Research, vol 43(9), p. 1911-1942, 2005. (see journal)

[2]  Caumond, A., Lacomme P., Moukrim A. and Tchernev N.,”A MILP for scheduling problems in an FMS with one vehicle”, submitted to European Journal of Operational Research, 2006.

[3] Lacomme P. and N. Tchernev, "Resolution of a Job-Shop Problem with a Single Transport Robot and Buffer Facilities". Submitted to International Conference on Service Systems and Service Management. Troyes, October 25-27, 2006. (see web server)