Process scheduling system, method, and program

• US 9,409,230 B2
• Filed: 05/06/2010
• Issued: 08/09/2016
• Est. Priority Date: 05/13/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hama, Toshiyuki, Yoshizumi, Takayuki
• Primary Examiner(s): Fennema, Robert
• Assistant Examiner(s): Garland, Steven R.
• Application Number:
  US13/320,406
• Publication Number:
  US 20120078407A1
• Time in Patent Office: 2,287 Days
• Field of Search: 700/104
• US Class Current: 1/1
• CPC Class Codes: B21B 13/22 for rolling metal immediately subsequent to continuous casting, i.e. in-line rolling of steelmethods therefor B21B1/46; continuous casting B22D11/00, e.g. into moulds with rolls B22D11/06
• CPC Class Codes: B21B 37/00 Control devices or methods specially adapted for metal-rolling mills or the work produced thereby methods or devices for measuring specially adapted for metal-rolling mills B21B38/00
• CPC Class Codes: B22D 11/12 Accessories for subsequent treating or working cast stock in situ rolling immediately subsequent to continuous casting B21B1/46, B21B13/22
• CPC Class Codes: B22D 11/1206 for plastic shaping of strands rolling mills B21B1/46
• CPC Class Codes: B22D 11/142 for curved casting
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G05B 2219/32298 Designate at least two group of articles, first with priority, reschedule second
• CPC Class Codes: G05B 2219/32336 Normal, special order lines share some common machines, part of production line
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

System, method and computer program product for combined scheduling of two different slab sequences by a rational technique. A two-dimensional grid graph having a direct slab sequence as a first dimension and an inventory slab sequence as a second dimension is prepared by processing of a computer as a data structure represented on a memory or a hard disk drive of the computer. A processing program of the computer generates two child nodes corresponding to a direct slab and an inventory slab, in each node of the two-dimensional graph according to a predetermined algorithm. By defining an appropriate weighting function, the processing program of the computer weights edges between nodes in the two-dimensional grid graph. After forming the weighted graph on a storage device of the computer such as the memory or the hard disk drive, the processing program of the computer calculates a path from a start point to an end point as a shortest path search problem.

Claims

1. A method for determining a sequence of slabs fed to a hot rolling mill from an inventory slab sequence and a direct slab sequence according to processing of a computer, comprising the steps of:

representing data of the inventory slab sequence and data of the direct slab sequence on a storage device operatively connected to a processing unit of the computer as a data structure arranged respectively in first and second directions;

forming a grid graph having intersections as nodes, from the data of the inventory slab sequence in the first direction and the data of the direct slab sequence in the second direction, wherein each node in the grid graph includes both;

(a) an inventory slab subnode for an inventory slab in an i position of the inventory slab sequence, wherein i is an integer; and

(b) a direct slab subnode for a direct slab in a j position of the direct slab sequence, wherein j is an integer;

weighting edges in the grid graph based on attributes of each slab in the inventory slab sequence and attributes of each slab in the direct slab sequence, wherein the weighting is performed using three indices that are inter-slab connectivity, a hot rolling idle time, and a direct slab wait time, said weight of each edge in the grid graph being calculated as a function of said three indices, an indice having a direct slab or inventory slab and corresponding direct slab subnode or inventory slab subnode as arguments;

determining a combined slab sequence of the inventory slab sequence and the direct slab sequence, by a shortest path search through a sequence of nodes from a start point to an end point in the weighted grid graph, said shortest path search traversing through either one of;

said inventory slab subnode or said direct slab subnode at each node of said sequence;

wherein said processing unit performs one or more said forming, weighting and determining;

wherein the inter-slab connectivity is determined by the function;

connectivity(slab1, slab2);

=C1*abs(slab1.width−

slab2.width)+C2*abs(slab1.thickness−

slab2.thickness); and

wherein slab1.width is width of slab1, slab2.width is width of slab 2, slab1.thickness is thickness of slab1, slab2.thickness is thickness of slab2, and

wherein C1 and C2 are positive constants and abs is a function that returns an absolute value; and

using the combined slab sequence to schedule feeding slabs to the hot rolling mill.

2. The method according to claim 1, wherein the shortest path search is Dijkstra'"'"'s algorithm.

3. The method according to claim 1, further comprising performing by said processing unit

a step of generating a child node corresponding to an inventory slab and a child node corresponding to a direct slab, respectively for the inventory slab subnode and the direct slab subnode.

4. The method according to claim 3, further comprising:

calculating a child node attribute for each said child node corresponding to an inventory slab and corresponding to a direct slab, at least one of said three indices being a function of said child node attribute.

5. The method according to claim 1, wherein a node-to-node transition takes one of four paths in said weighted graph.

6. The method according to claim 1, wherein said function of said three indices is a summation of the three indices to which a weight is assigned.

7. The method according to claim 1, wherein said weight of each edge in the grid graph is a value that varies along a continuum based upon said three indices.

8. A non-transitory computer program product for determining a sequence of slabs fed to a hot rolling mill from an inventory slab sequence and a direct slab sequence comprising:

a computer usable medium having computer usable program code embodied therewith, the computer usable program code comprising;

computer usable program code configured to represent data of the inventory slab sequence and data of the direct slab sequence on a storage means of the computer as a data structure arranged respectively in first and second directions;

computer usable program code configured to form a grid graph having intersections as nodes, from the data of the inventory slab sequence in the first direction and the data of the direct slab sequence in the second direction, wherein each node in the grid graph includes both;

(a) an inventory slab subnode for an inventory slab in an i position of the inventory slab sequence, wherein i is an integer; and

(b) a direct slab subnode for a direct slab in a j position of the direct slab sequence, wherein j is an integer;

computer usable program code configured to weight edges in the grid graph based on attributes of each slab in the inventory slab sequence and attributes of each slab in the direct slab sequence, wherein the weighting is performed using three indices that are inter-slab connectivity, a hot rolling idle time, and a direct slab wait time, said weight of each edge in the grid graph being calculated as a function of said three indices, an indice having a direct slab or inventory slab and corresponding direct slab subnode or inventory slab subnode as arguments;

computer usable program code configured to determine a combined slab sequence of the inventory slab sequence and the direct slab sequence, by a shortest path search through a sequence of nodes from a start point to an end point in the weighted grid graph, said shortest path search traversing through either one of;

said inventory slab subnode or said direct slab subnode at each node of said sequence;

wherein the inter-slab connectivity is determined by the function;

connectivity(slab1, slab2);

=C1*abs(slab1.width−

slab2.width)+C2*abs(slab1.thickness−

slab2.thickness); and

wherein slab1.width is width of slab1, slab2.width is width of slab 2, slab1.thickness is thickness of slab1, slab2.thickness is thickness of slab2, and

wherein C1 and C2 are positive constants and abs is a function that returns an absolute value; and

using the combined slab sequence to schedule feeding slabs to the hot rolling mill.

9. The computer program product according to claim 8, wherein the shortest path search is Dijkstra'"'"'s algorithm.

10. The computer program product according to claim 8, wherein the computer usable program code is further configured to execute generating a child node corresponding to an inventory slab and a child node corresponding to a direct slab, respectively for the inventory slab subnode and the direct slab subnode.

11. The method according to claim 10, further comprising:

calculating a child node attribute for each said child node corresponding to an inventory slab and corresponding to a direct slab, at least one of said three indices being a function of said child node attribute.

12. The computer program product according to claim 8, wherein a node-to-node transition takes one of four paths in said weighted graph.

13. The computer program product according to claim 8, wherein said function of said three indices is a summation of the three indices to which a weight is assigned.

14. The computer program product according to claim 8, wherein said weight of each edge in the grid graph is a value that varies along a continuum based upon said three indices.

15. A system for determining a sequence of slabs fed to a hot rolling mill from an inventory slab sequence and a direct slab sequence according to processing of a computer, comprising:

a memory storage device for storing data of the inventory slab sequence and data of the direct slab sequence;

a processing device operatively connected to said memory storage device and configured for performing a method comprising;

representing the data of the inventory slab sequence and the data of the direct slab sequence on the storage means of the computer as a data structure arranged respectively in first and second directions;

forming a grid graph having intersections as nodes, from the data of the inventory slab sequence in the first direction and the data of the direct slab sequence in the second direction, wherein each node in the grid graph includes both;

(a) an inventory slab subnode for an inventory slab in an i position of the inventory slab sequence, wherein i is an integer; and

(b) a direct slab subnode for a direct slab in a j position of the direct slab sequence, wherein j is an integer;

weighting edges in the grid graph based on attributes of each slab in the inventory slab sequence and attributes of each slab in the direct slab sequence, wherein the weighting is performed using three indices that are inter-slab connectivity, a hot rolling idle time, and a direct slab wait time, said weight of each edge in the grid graph being calculated as a function of said three indices, an indice having a direct slab or inventory slab and corresponding direct slab subnode or inventory slab subnode as arguments;

determining a combined slab sequence of the inventory slab sequence and the direct slab sequence, by a shortest path search through a sequence of nodes from a start point to an end point in the weighted grid graph, said shortest path search traversing through either one of;

said inventory slab subnode or said direct slab subnode at each node of said sequence;

wherein the inter-slab connectivity is determined by the function;

connectivity(slab1, slab2);

=C1*abs(slab1.width−

slab2.width)+C2*abs(slab1.thickness−

slab2.thickness); and

wherein slab1.width is width of slab1, slab2.width is width of slab 2, slab1.thickness is thickness of slab1, slab2.thickness is thickness of slab2, and

wherein C1 and C2 are positive constants and abs is a function that returns an absolute value; and

using the combined slab sequence to schedule feeding slabs to the hot rolling mill.

16. The system according to claim 15, wherein the shortest path search is Dijkstra'"'"'s algorithm.

17. The system according to claim 15, wherein said processor device is further configured to perform

generating a child node corresponding to an inventory slab and a child node corresponding to a direct slab, respectively for the inventory slab subnode and the direct slab subnode.

18. The system according to claim 15, wherein said weight of each edge in the grid graph is a value that varies along a continuum based upon said three indices.