*** Data accompanying the research on CGL Scheduling Problem ***
Author: Alvarez-Gil, N. (Nicolás) (uo226901@uniovi.es)
Business Management Department, Polytechnic School of Engineering of Gijón, University of Oviedo


*** Dataset description ***
This dataset contains the cost matrix of several instances of the scheduling problem of a Continuous Galvanizing Line (CGL). They are real instances of a CGL of a 
Spanish steel company, in which a fixed group of steel coils should be sequenced. The cost of sequencing two coils together can be:

 - A cost (c[i,j] != -1): in this case it is possible to produce coil i right before coil j, and the value c[i,j] represents the actual production cost.
 - A constraint (c[i,j] = -1): in this case coil i cannot be produced right before coil j because of technical limitations of the line (coil i cannot link directly to coil j, but
   it can be produced at any other positions before coil j).


The problem consists in finding a minimum-cost Hamiltonian path: a minimum-cost sequence that contains all the nodes just once.
The main challenge is to find a feasible sequence: a sequence without constraints.
The costs are asymmetric: cost[i,j] != cost[j,i]

The name of the instances follows the notation cgl_X:
  X = the size of the instances(the total number of coils to be sequenced)

ALL the instances are known to be sequenceable: it exist a Hamiltonian path (*)
  
The challenge is to find an algorithm able to provide minimum-cost feasible solutions for all the instances.
 

 
 
*** Example ***

The instance "cgl_17.txt" contains the following matrix:

-1;300;-1;654;926;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1
305;-1;963;117;237;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1
952;493;-1;704;686;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1
678;123;-1;-1;41;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1
946;237;1155;34;-1;804;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1;-1
-1;-1;-1;-1;-1;-1;71;1721;-1;-1;-1;-1;-1;-1;-1;-1;-1
-1;-1;-1;-1;-1;73;-1;1777;-1;-1;-1;-1;-1;-1;-1;-1;-1
-1;-1;-1;-1;-1;2034;2020;-1;634;634;634;634;634;634;634;634;67
-1;-1;-1;-1;-1;-1;-1;685;-1;0;0;0;0;0;0;0;308
-1;-1;-1;-1;-1;-1;-1;685;0;-1;0;0;0;0;0;0;308
-1;-1;-1;-1;-1;-1;-1;685;0;0;-1;0;0;0;0;0;308
-1;-1;-1;-1;-1;-1;-1;685;0;0;0;-1;0;0;0;0;308
-1;-1;-1;-1;-1;-1;-1;685;0;0;0;0;-1;0;0;0;308
-1;-1;-1;-1;-1;-1;-1;685;0;0;0;0;0;-1;0;0;308
-1;-1;-1;-1;-1;-1;-1;685;0;0;0;0;0;0;-1;0;308
-1;-1;-1;-1;-1;-1;-1;685;0;0;0;0;0;0;0;-1;308
-1;-1;-1;-1;-1;-1;-1;77;293;293;293;293;293;293;293;293;-1


The size of the instance is equal to the size of the square matrix, and the solution must be a sequence of the same size with each node appearing
just once. 

The element (i,j) of the matrix represent the cost of processing coil i right before coil j.

From Row 1:
[0, 0]:   (Coil 0 -> Coil 0) = -1 (not possible, each coil must appear just once in the sequence)
[0, 1]:   (Coil 0 -> Coil 1) = 300 (cost of producing coil 0 right before coil 1)
[0, 2]:   (Coil 0 -> Coil 2) = -1 (not possible, technical constraint)
[0, 3]:   (Coil 0 -> Coil 3) = 654 (cost of producing coil 0 right before coil 3)
[0, 4]:   (Coil 0 -> Coil 4) = 926 (cost of producing coil 0 right before coil 4)
(...)

From Row 2:
[1, 0]:   (Coil 1 -> Coil 0) = 305 (cost of producing coil 1 right before coil 0)
[1, 1]:   (Coil 1 -> Coil 1) = -1 (not possible, each coil must appear just once in the sequence)
[1, 2]:   (Coil 1 -> Coil 2) = 963 (cost of producing coil 1 right before coil 2)
[1, 3]:   (Coil 1 -> Coil 3) = 117 (cost of producing coil 1 right before coil 3)
[1, 4]:   (Coil 1 -> Coil 4) = 237 (cost of producing coil 1 right before coil 4)
(...)


A possible solution for this instance is:
Seq = [2, 0, 1, 3, 4, 5, 6, 7, 16, 11, 15, 10, 8, 12, 14, 13, 9]
Cost = 952 + 300 + 117 + 41 + 804 + 71 + 1777 + 67 + 293 + 0 + 0 + 0 + 0 + 0 + 0 + 0 =  4422




*** Additional Comment ***

 (*) For all the instances, the sequence [0, 1, 2, 3, 4, 5, ..., n-1] (being n the size of the instance) is a feasible sequence, but the 
algorithm should be able to find a minimun-cost feasible sequence without using this information.