UDK 669.18:658.5 Original scientific article/lzvirni znanstveni članek ISSN 1580-2949 MTAEC9, 46(3)269(2012) BATCH-FlLLlNG SCHEDULING AND PARTICLE SWARMS IZDELAVA DELOVNIH NALOGOV ZA JEKLARNO IN ROJl DELCEV Miha Kovacic1, Božidar Šarler2 1ŠTORE STEEL, d. o. o., Železarska cesta 3, Sl-3220 Štore, Slovenia 2Laboratory for Multiphase Processes, University of Nova Gorica, Vipavska 13, Sl-5000, Nova Gorica, Slovenia miha.kovacic@store-steel.si Prejem rokopisa - received: 2011-10-24; sprejem za objavo - accepted for publication: 2012-01-31 Štore Steel Ltd faces a problem of producing a large number (approximately 1400) of different steel compositions in relatively small quantities (approximately 15 t). This production is performed in batches of predetermined quantities (50-53 t). The purpose of this paper is to present a methodology for optimizing the production of predetermined steel grades in predetermined quantities before the customers' deadline and in such a way as to reduce the non-planned and ordered quantities with the date before the deadline and minimize the number of batches. The particle-swarm method was used for the optimization. The results of the research have been used in practice since 2006. Since then the production of non-planned and ordered quantities were reduced from 17.17 % to 10.12 %. Keywords: steelmaking, continuous casting, steel grade, work orders, scheduling, optimization, particle-swarm optimization Štore Steel, d. o. o., se spopada s problemom majhnih naročil (v povprečju 15 t) ter izdelavo ogromne količine različnih kvalitet jekla (več kot 1400). Jeklo se izdeluje v šaržah (50-53 t). V članku je predstavljena metodologija za optimiranje izdelave planiranih kvalitet in količin jekla v predvidenem roku z namenom, da se zmanjša odlita planirana količina jekla, kjer je dobavni rok daljši kot določeni, ter neplanirana količina jekla. Optimizacija je bila izvedena z roji delcev. Rezultati raziskave so uporabljeni v praksi od leta 2006, ko sta se v letu 2007 odlita planirana količina jekla, kjer je dobavni rok daljši kot določeni, ter neplanirana količina jekla, zmanjšali iz 17,17 % na 10,12 %. Ključne besede: jeklarstvo, kontinuirano odlivanje, kvaliteta jekla, delovni nalogi, planiranje, optimizacija, optimizacija z roji delcev 1 INTRODUCTION Štore Steel Ltd owns a small (200 000 t per year) flexible steel plant and is one of the best-known producers of flat spring steel in Europe. The company produces more than 80 steel grades with more than 1400 different customer-specific chemical compositions. ln the steel plant, scrap iron is melted in a 60 t-capacity electric arc furnace. The liquid steel is then poured into the ladle (ca. 53 t), which a crane transports to a subsequent ladle furnace, where manganese, chromium, molybdenum, nickel, vanadium and other alloying elements are added to the steel in order to meet the chemical-quality requirements. The molten steel is cast into square billets with the dimensions of 140 mm or 180 mm in a continuous caster. The billets are reheated afterwards and the steel bars of various shapes and dimensions are manufactured by means of hot rolling and finally in line with the customers' expectations, heat treated, peeled, drawn or grinded. The steelmaking and casting represent the basic steel-production operations and play a primary role in the downstream steel production. The optimization of casting the planned batches in line with the different requirements relating to a chemical composition, ordering dates, casting quantities, etc., is an extremely challenging task. The complexity of batch planning increases with the number of different steel grades and different customers' orders. There is a lack of descriptions of batch-filling scheduling in the open literature. The most plausible reasons for this are the reluctance of the manufacturers to expose their well-understood heuristics for forming the production schedules, and different technology or hardware specifics1-3. On the other hand, there are plenty of publications on casting technology and physical modelling available4-9 at present. One of the principal problems in the steel-production scheduling2 is determining the scheduling of operations to be performed on molten steel during the production stage involving steelmaking and continuous casting. A theoretical basis for the time-dependent batch scheduling is, to the best of the authors' knowledge, presented only in10,11. Similarly,12 explores the scheduling problem involving the production and the transportation in a steelmaking shop in order to minimize the completion time. Paper13 deals with the schedules for casting different moulds from a number of heats, and14 deals with the scrap-charge-optimization problem, on the basis of its chemical composition, in the secondary steel production. The last reference is most probably the most relevant with respect to the batch-filling scheduling, discussed in the present paper. To a great extent, at [tore Steel Ltd work-order scheduling and the related tasks have been traditionally carried out by a highly skilled, expert, human scheduler. In the present paper, the particle-swarm method was considered for the generation of batch-filling schedules. During the optimization the particles 'fly' intelligently in the solution space and search for the optimal batch-filling schedules in line with the strategies of the particle-swarm algorithm. Many different work-order schedules were obtained during the optimization. 2 STRUCTURE OF WORK ORDERS The production of steel at Štore Steel Ltd is usually deliberately carried out for a pool of 384 customers. The mean cast quantity is 14.32 t (a standard deviation of 23.77 t). Due to the constraints posed by the production, some extra cast steel is produced on top of the ordered cast quantity. This is denoted as a non-planned cast quantity. The work orders for batch processing are generated on the basis of the customers' orders. A typical structure of work orders is presented in Table 1. A work-order number is a sequential number. The cover-quality prescription and the work-order chemical limitations define the chemical composition of the related batch. Each quality prescription includes also its own steelmaking technology (i.e., the times, temperatures, sampling, purging, oxygen activities). There are, in general, two groups of steelmaking technologies: the first is used for the extra-machinability steels15, where the batch weight is 50 t, and the second is appropriate for the other steel qualities, where the batch weight is 53 t. In the extra-machinability steelmaking technology the Table 1: Work-order example Tabela 1: Zgled oblike delovnega naloga Work order number: 0001019 Cover quality prescription code Chemical limitations 732.59.2 wt% C 0.52-0.54! wt% P MAX 0.015! wt% Sn MAX 0.02! wt% As MAX 0.04! Quality prescription code Customer order code Ordered quantity (tons) Delivery date 732.54.2 0000855022 25 30.1.2009 732.01.0 0000937001 3.5 8.11.2009 732.59.2 0000855007 1.5 30.1.2009 732.59.2 Non-planned cast quantity 23 molten steel in the ladle is more reactive, so the molten steel quantity (batch weight) should be smaller. Tables 2, 3 and 4 show three sample-quality prescriptions (732.00.1, 732.59.2, 732.54.2) and their calculated chemical limits. The chemical limitations are calculated on the basis of the quality-prescription limits and the simple instructions presented in Figures 1 and 2. If the chemical target value for a chemical element is prescribed in a quality prescription, it means that the ladle-furnace operator has to obtain the exact chemical weight percentage of the element. The internal minimum and maximum are prescribed in line with the technology procedure. The batch satisfies a customer's chemical requirements if the chemical weight percentage is within the customer's limits (minimum and maximum). Due to the technology limitations and instructions, the customers' chemical limitations are converted to internal composition limits so as to assure the customers' specifications. The briefly described instructions dictate that the in-plant chemical limitations are more restrictive than the customers' chemical limitations. Table 2: Quality prescription 732.01.0 and its calculated chemical limits (minimum and maximum) Tabela 2: Kakovostni predpis 732.01.0 in izračunane kemične omejitve (minimum in maksimum) Quality prescription 732.01.0 Calculated chemical limits Element Customer minimum (wt%) Internal minimum (wt%) Aim (wt%) Internal maximum (wt%) Customer maximum (wt%) Quality prescription limits -minimum (wt%) Quality prescription limits -maximum (wt%) C 0.47 0.50 0.53 0.55 0.47 0.55 Si 0.15 0.20 0.35 0.40 0.15 0.40 Mn 0.70 0.80 1.00 1.10 0.70 1.10 P 0.015 0.025 0 0.025 S 0.020 0.025 0 0.025 Cr 0.90 1.00 1.10 1.20 0.90 1.20 Mo 0.05 0.08 0 0.08 Ni 0.25 0.30 0 0.30 Al 0.010 0.011 0.015 0.100 0.010 0.015 Cu 0.25 0.40 0 0.40 V 0.10 0.14 0.17 0.20 0.10 0.20 Sn 0.030 0 0.030 As 0 100 N 0 100 Table 3: Quality prescription 732.54.2 and its calculated chemical limits (minimum and maximum) Tabela 3: Kakovostni predpis 732.54.2 in izra~unane kemi~ne omejitve (minimum in maksimum) Quality prescription 732.54.2 Calculated chemical limits Element Customer minimum (wt%) Internal minimum (wt%) Aim (wt%) Internal maximum (wt%) Customer maximum (wt%) Quality prescription limits -minimum (wt%) Quality prescription limits -maximum (wt%) C 0.49 0.50 0.52 0.54 0.49 0.54 Si 0.20 0.20 0.34 0.35 0.40 0.20 0.40 Mn 0.90 0.91 1.00 1.10 0.90 1.10 P 0.015 0.015 0 0.015 S 0.015 0.015 0 0.015 Cr 0.90 0.91 1.00 1.20 0.90 1.20 Mo 0.04 0.08 0 0.08 Ni 0.10 0.20 0 0.20 Al 0.010 0.010 0.011 0.015 0.025 0.010 0.025 Cu 0.25 0.25 0 0.25 V 0.10 0.11 0.14 0.20 0.10 0.20 Sn 0.015 0 0.015 As 0.035 0.040 0 0.040 N 0 100 Table 4: Quality prescription 732.59.2 and its calculated chemical limits (minimum and maximum) Tabela 4: Kakovostni predpis 732.59.2 in izra~unane kemi~ne omejitve (minimum in maksimum) Quality prescription 732.59.2 Calculated chemical limits Element Customer minimum (wt%) Internal minimum (wt%) Aim (wt%) Internal maximum (wt%) Customer maximum (wt%) Quality prescription limits -minimum (wt%) Quality prescription limits -maximum (wt%) C 0.51 0.52 0.52 0.55 0.55 0.52 0.55 Si 0.25 0.25 0.34 0.35 0.40 0.25 0.35 Mn 0.95 1.00 1.00 1.10 1.10 1.00 1.10 P 0.015 0.020 0 0.020 S 0.008 0.008 0 0.008 Cr 1.05 1.10 1.10 1.20 1.20 1.10 1.20 Mo 0.05 0.06 0 0.05 Ni 0.20 0.20 0 0.20 Al 0.010 0.011 0.015 0.040 0.010 0.015 Cu 0.25 0.25 0 0.25 V 0.10 0.15 0.16 0.18 0.25 0.15 0.18 Sn 0.025 0 0.025 As 0 100 N 0.016 0 0.016 In fact, all three of the quality prescriptions presented, match the chemical composition of the 50CrV4 (W. NR. 1.8159) spring steel. For example, at the moment there are 53 quality prescriptions for the 50CrV4 steel existing in the company, and it is not possible to chemically combine all of them. On the basis of the selected customers' orders and their quality prescriptions (732.00.1, 732.59.2, 732.54.2), it Figure 1: Instructions for defining the quality-prescription minimum limit Slika 1: Pravila za dolo~anje minimuma kakovostnega predpisa Figure 2: Instructions for defining the quality-prescription maximum limit Slika 2: Pravila za dolo~anje maksimuma kakovostnega predpisa Table 5: Batch chemical limitations Tabela 5: Kemijske omejitve šarže Quality prescription 732.01.0 limits (wt%) Quality prescription 732.54.2 limits (wt%) Quality prescription 732.59.2 limits (wt%) Batch chemical limitations (wt%) Element Minimum Maximum Minimum Maximum Minimum Maximum Minimum Maximum C 0.47 0.55 0.49 0.54 0.52 0.55 0.52 0.54 Si 0.15 0.40 0.20 0.40 0.25 0.35 0.25 0.35 Mn 0.70 1.10 0.90 1.10 1.00 1.10 1.00 1.10 P 0 0.025 0 0.015 0 0.020 0 0.015 S 0 0.025 0 0.015 0 0.008 0 0.008 Cr 0.90 1.20 0.90 1.20 1.10 1.20 1.10 1,2 Mo 0 0.08 0 0.08 0 0.05 0 0.05 Ni 0 0.30 0 0.20 0 0.20 0 0.20 Al 0.010 0.015 0.010 0.025 0.010 0.015 0.010 0.015 Cu 0 0.40 0 0.25 0 0.25 0 0.25 V 0.10 0.20 0.10 0.20 0.15 0.18 0.15 0.18 Sn 0 0.030 0 0.015 0 0.025 0 0.015 As 0 100 0 0.040 0 100 0 0.040 N 0 100 0 100 0 0.016 0 0.016 is possible to easily calculate the batch chemical limitations (Table 5) in line with the instructions in Figures 1 and 2. The logic for defining the cover-quality prescription is as follows: The quality prescription with the highest number of chemical-element limitations among the selected work-order quality prescriptions is defined as the cover quality prescription. In such a case, the ladle operator uses the technology prescribed in line with the cover-quality prescription and adjusts the steelmaking technology according to the required chemical composition. In the case of a customer's order for the extra-machinability steels included in the work-order quality prescriptions, its quality prescription automatically becomes a cover quality prescription. 3 PARTICLE-SWARM BATCH SCHEDULING At the beginning of a batch scheduling, a grouping based on the ordered quantities is performed. The ordered quantities are divided into groups with a similar chemical composition. An ordered quantity fits into a group if the group already includes one or more ordered quantities with a similar chemical composition (a similar quality prescription). After the grouping of the ordered quantities the particle-swarm method is used for the batch-filling scheduling14. part of ordered quantity 3 part of orderec quantity 4 3art of orderec quantity 3 No n-planned quantity ordered quantity 2 ordered quantity 1 part of ordered quantity 3 part of ordered quantity 4 Figure 3: Work order schedule - the organism Slika 3: Nabor delovnih nalogov - organizem The "particle" structure is conditioned with the nature of the problem - the consecutive events - that the batch is cast consecutively. The biggest problem is in dealing with the batch-filling schedule - an organism evaluation. 4 BATCH-FILLING SCHEDULES AS PARTICLES The batch-filling schedules are in fact the work-order sequences and can be presented as a sequence of batches with the ordered quantities (Figure 3). Figure 3 shows the customer's ordered quantities cast within 4 batches. The ordered quantity 3 is cast within 3 batches, the ordered quantity 4 within 2 batches, and all the other ordered quantities within one batch. The non-planned cast quantity can be found in the last batch - batch 4. Hence, the organism in Figure 3 can be written down as a sequence: Ordered quantity 1 - Ordered quantity 2 -Ordered quantity 3 - Ordered quantity 4. The principal task is to form a batch-filling sequence based on a customer's ordered cast quantities, quality prescriptions, delivery dates, and any other instructions. 5 FORMATION AND EVALUATION OF WORK ORDERS The deadline must be defined in terms of the delivery date for the ordered quantities. This means that all quantities should be cast in terms of that delivery date. The batch weight is defined in line with the steelmaking technology - for extra-machinability steels, the batch weight is 50 t and for the other steel qualities the batch weight is 53 t. Individually ordered quantities from the ordered-quantities pool are added to the work order until the batch weight is reached. If the last added quantity exceeds the batch weight, which is usually the case, a partial quantity is added to one or more consecutive work orders. As a rule, partial quantities are added to the consecutive work order only when they exceed 5 %. Small orders of up to 5 t should not be split between different batches, i.e., they should be cast within one batch. For each ordered quantity, the chemical composition is checked against the quality prescriptions for the added quantity as well. In the event that a chemical composition does not fit the chemical prescriptions for the added quantities, the actual work order is filled with a non-planned quantity and the quantity is added to the consecutive work order (orders), which is (are) filled according to the previously mentioned guidelines. The work orders for quantities with a delivery date beyond the defined deadline are automatically abandoned. The evaluation of a work-order schedule consists of the following three parts: 01 The number of additional ordered quantities, where the ordered quantities are not cast within one batch (for instance, as seen in Figure 3, we have to cast the ordered quantity 3 in 2 additional batches, and the ordered quantity 4 in one additional batch, so that the total number of additional ordered quantity parts, where the ordered quantities are not cast within one batch is, in this case, 3); 02 Non-planned cast quantities in tons; Table 6: Quality-prescription quantities in October 2009 and their calculated chemical limits Tabela 6: Koli~ine za kakovostne predpise v oktobru 2009 in njihove izra~unane kemijske omejitve Quality Prescription code Steel quality Ordered Quantity (tons) C (wt%) Si (wt%) Mn (wt%) P (wt%) S (wt%) C (wt%)r M (wt%)o Ni (wt%) Al (wt%) Cu (wt%) V (wt%) Sn (wt%) As (wt%) N (wt%) 108.15.0 44MnSiVS6 30.192 0.42-0.47 0.5-0.7 1.3-1.6 MAX 0.035 0.02-0.035 MAX 0.25 MAX 0.07 MAX 0.25 0.016-0.03 MAX 0.25 0.1-0.13 MAX 0.03 108.33.0 38MnVS5 121.5 0.35-0.4 0.5-0.7 1.2-1.5 MAX 0.035 0.045-0.06 0.15-0.25 MAX 0.08 MAX 0.3 0.02-0.038 MAX 0.25 0.08-0.13 MAX 0.03 0.015-0.018 108.70.1 38MnVS6 (extra machinability) 18.944 0.41-0.44 0.3-0.5 1.1-1.4 MAX 0.035 0.03-0.035 0.15-0.25 MAX 0.08 0.15-0.25 0.01-0.03 MAX 0.3 0.13-0.15 MAX 0.03 0.011-0.02 127.11.5 61SiCr7 83.841 0.57-0.65 1.6-1.8 0.7-1 MAX 0.02 MAX 0.015 0.25-0.4 MAX 0.08 MAX 0.3 0.015-0.025 MAX 0.25 MAX 0.1 MAX 0.02 140.11.1 CSN 15230.3 18.038 0.24-0.34 0.17-0.37 0.4-0.8 MAX 0.035 MAX 0.035 2.2-2.5 MAX 0.05 MAX 0.2 0.02-0.035 MAX 0.25 0.1-0.2 MAX 0.03 193.31.0 27MnCrB5 18.352 0.25-0.3 0.15-0.35 1-1.4 MAX 0.035 MAX 0.035 0.3-0.6 MAX 0.05 MAX 0.2 0.02-0.035 MAX 0.25 MAX 0.05 MAX 0.03 193.52.0 30MnB5 26.374 0.27-0.3 0.1-0.3 1.05-1.2 MAX 0.035 MAX 0.035 MAX 0.3 MAX 0.08 MAX 0.3 0.02-0.035 MAX 0.4 MAX 0.1 MAX 0.02 193.54.0 28MnCrB7-2 53.872 0.26-0.28 0.15-0.25 1.68-1.78 MAX 0.03 0.02-0.04 0.48-0.53 MAX 0.1 MAX 0.3 0.02-0.05 MAX 0.25 MAX 0.1 MAX 0.02 MAX 0.012 503.14.0 St 37-2 4.019 0.14-0.17 0.15-0.5 0.4-1.4 MAX 0.035 MAX 0.035 MAX 0.3 MAX 0.08 MAX 0.3 0.02-0.035 MAX 0.4 MAX 0.1 MAX 0.03 MAX 0.009 503.31.1 RSt 37-2 97.65 0-0.08 0-0.08 0.28-0.45 MAX 0.02 MAX 0.02 0.015-0.025 MAX 0.012 516.17.1 Cm45 13.616 0.43-0.48 0.15-0.35 0.6-0.7 MAX 0.035 0.02-0.035 0.17-0.23 MAX 0.07 MAX 0.25 0.01-0.05 MAX 0.25 MAX 0.05 MAX 0.03 523.00.0 C75 46.176 0.7-0.8 0.15-0.35 0.6-0.8 MAX 0.045 MAX 0.045 MAX 0.3 MAX 0.08 MAX 0.3 0.02-0.1 MAX 0.4 MAX 0.1 MAX 0.03 524.11.0 C70 0.918 0.65-0.75 0.25-0.35 0.8-0.9 MAX 0.02 MAX 0.02 0.2-0.3 MAX 0.05 MAX 0.2 0.015-0.05 0.05-0.25 MAX 0.1 MAX 0.03 615.12.0 C22E 30.251 0.16-0.19 MAX 0.1 0.3-0.4 MAX 0.015 MAX 0.015 MAX 0.2 MAX 0.1 MAX 0.2 0.02-0.035 MAX 0.2 MAX 0.05 MAX 0.03 623.32.0 70MnVS4 218.093 0.69-0.72 0.15-0.25 0.8-0.9 MAX 0.015 0.06-0.07 0.1-0.2 MAX 0.06 MAX 0.2 MAX 0.03 MAX 0.25 0.14-0.15 MAX 0.03 0.013-0.016 625.13.1 C50 105.08 0.5-0.53 0.2-0.35 0.8-0.9 MAX 0.03 0.015-0.02 0.23-0.3 MAX 0.08 0.15-0.24 0.02-0.035 MAX 0.25 MAX 0.1 MAX 0.03 0.008-0.013 635.36.5 C35R 23.088 0.36-0.39 0.2-0.4 0.65-0.8 MAX 0.03 0.02-0.035 0.2-0.3 MAX 0.08 MAX 0.3 0.02-0.03 MAX 0.25 MAX 0.1 MAX 0.03 636.11.1 C45 515.41 0.47-0.5 0.2-0.35 0.7-0.8 MAX 0.035 0.02-0.025 0.24-0.29 MAX 0.08 0.15-0.2 0.02-0.035 MAX 0.25 MAX 0.1 MAX 0.03 0.008-0.013 705.13.3 SAE1141 54.6 0.39-0.43 0.2-0.3 1.4-1.55 MAX 0.03 0.08-0.092 MAX 0.3 MAX 0.08 MAX 0.3 0.015-0.02 MAX 0.3 711.00.1 41Cr4 26.869 0.38-0.45 0.2-0.4 0.6-0.9 MAX 0.035 MAX 0.035 0.9-1.2 MAX 0.08 MAX 0.3 0.02-0.1 MAX 0.4 MAX 0.1 MAX 0.03 711.14.0 41Cr4 15.333 0.38-0.45 0.2-0.4 0.6-0.9 MAX 0.035 MAX 0.035 0.9-1.2 MAX 0.08 MAX 0.3 0.02-0.1 MAX 0.4 MAX 0.1 MAX 0.03 718.70.2 16MnCr5 (extra machinability) 55.388 0.14-0.19 0.2-0.4 1-1.3 MAX 0.035 0.02-0.035 0.8-1.1 MAX 0.08 MAX 0.3 0.02-0.1 MAX 0.4 MAX 0.1 MAX 0.03 MAX 0.015 724.24.0 42CrMo4 38.438 0.38-0.45 0.15-0.4 0.6-0.9 MAX 0.035 0.02-0.035 0.9-1.2 0.15-0.3 MAX 0.25 0.02-0.045 MAX 0.25 MAX 0.1 MAX 0.03 732.01.0 50CrV4 150.341 0.47-0.55 0.15-0.4 0.7-1.1 MAX 0.025 MAX 0.025 0.9-1.2 MAX 0.08 MAX 0.3 0.01-0.015 MAX 0.4 0.1-0.2 MAX 0.03 732.03.0 51CrV4 9.709 0.47-0.55 0.15-0.4 0.7-1.1 MAX 0.025 MAX 0.025 0.9-1.2 MAX 0.08 MAX 0.3 0.01-0.015 MAX 0.4 0.1-0.2 MAX 0.03 732.12.5 51CrV4 67.113 0.51-0.54 0.2-0.35 1-1.1 MAX 0.015 MAX 0.015 1.1-1.2 MAX 0.08 MAX 0.2 0.01-0.015 MAX 0.25 0.1-0.2 MAX 0.02 MAX 0.04 732.13.5 51CrV4 141.563 0.51-0.56 0.2-0.35 1-1.2 MAX 0.015 MAX 0.015 1.1-1.25 MAX 0.08 MAX 0.2 0.01-0.015 MAX 0.25 0.1-0.2 MAX 0.02 MAX 0.04 732.18.1 51CrV4 5.661 0.47-0.51 0.15-0.4 0.7-0.85 MAX 0.025 MAX 0.025 0.9-1 MAX 0.08 MAX 0.25 0.01-0.04 MAX 0.25 0.1-0.25 MAX 0.025 732.19.1 51CrV4 11.485 0.51-0.55 0.15-0.4 0.85-0.95 MAX 0.025 MAX 0.025 0.95-1.1 MAX 0.08 MAX 0.25 0.01-0.04 MAX 0.25 0.1-0.25 MAX 0.025 732.20.2 51CrV4 58.785 0.51-0.55 0.15-0.4 0.9-1.1 MAX 0.025 MAX 0.025 1.05-1.2 MAX 0.08 MAX 0.25 0.01-0.04 MAX 0.25 0.1-0.25 MAX 0.025 732.21.2 51CrV4 27.675 0.52-0.54 0.2-0.35 0.95-1.1 MAX 0.025 MAX 0.025 1.1-1.2 MAX 0.07 MAX 0.2 0.01-0.015 MAX 0.25 0.12-0.2 MAX 0.025 732.24.4 50CrV4 69.967 0.47-0.55 0.2-0.4 0.7-1.1 MAX 0.035 MAX 0.035 0.9-1.2 MAX 0.05 MAX 0.2 0.01-0.015 MAX 0.25 0.1-0.2 MAX 0.03 MAX 0.012 732.26.2 51CrV4 17.263 0.51-0.54 0.2-0.35 0.9-1.05 MAX 0.02 MAX 0.015 1-1.1 MAX 0.04 MAX 0.2 0.01-0.015 MAX 0.25 0.11-0.15 MAX 0.025 732.27.3 51CrV4 31.69 0.51-0.55 0.15-0.4 0.95-1.1 MAX 0.025 MAX 0.025 1.1-1.2 MAX 0.08 MAX 0.25 0.01-0.04 MAX 0.25 0.1-0.25 MAX 0.025 732.54.2 51CrV4 636.408 0.49-0.54 0.2-0.35 0.9-1.1 MAX 0.015 MAX 0.015 0.9-1.2 MAX 0.08 MAX 0.2 0.01-0.015 MAX 0.25 0.1-0.2 MAX 0.02 MAX 0.04 732.59.2 50CrV4 427.379 0.52-0.55 0.25-0.35 1-1.1 MAX 0.02 MAX 0.008 1.1-1.2 MAX 0.06 MAX 0.2 0.01-0.015 MAX 0.25 0.15-0.18 MAX 0.025 MAX 0.016 732.62.0 50CrV4 6.83 0.47-0.55 0.2-0.4 0.7-1.1 MAX 0.02 MAX 0.01 0.9-1.2 MAX 0.08 MAX 0.2 0.01-0.015 MAX 0.25 0.1-0.2 MAX 0.03 MAX 0.012 732.66.0 51CrV4 37.37 0.47-0.5 0.2-0.4 0.7-1.1 MAX 0.035 MAX 0.035 0.9-1.2 MAX 0.08 MAX 0.3 0.01-0.015 MAX 0.25 0.1-0.25 MAX 0.03 MAX 0.012 741.33.3 15CrNiS6 4.144 0.12-0.17 0.15-0.4 0.4-0.6 MAX 0.035 0.02-0.035 1.4-1.7 MAX 0.08 1.4-1.7 0.02-0.1 MAX 0.25 MAX 0.1 MAX 0.03 MAX 0.013 775.13.0 23MnNiMoCr5-4 25.693 0.21-0.24 0.15-0.25 1.25-1.4 MAX 0.02 MAX 0.012 0.5-0.6 0.5-0.6 1-1.1 0.02-0.05 MAX 0.25 MAX 0.1 MAX 0.02 MAX 0.012 779.27.1 16MnCrS5 414.9 0.14-0.17 0.2-0.35 1-1.1 MAX 0.035 0.02-0.03 0.8-0.9 MAX 0.05 MAX 0.15 0.02-0.03 MAX 0.25 MAX 0.1 MAX 0.03 MAX 0.013 779.71.4 16MnCrS5 (extra machinability) 40.848 0.17-0.19 0.15-0.3 1-1.1 MAX 0.025 0.03-0.035 0.9-1 MAX 0.07 MAX 0.15 0.02-0.03 MAX 0.28 MAX 0.1 MAX 0.02 0.01-0.012 780.10.0 20MnCrS5 52.8 0.2-0.23 0.15-0.25 1.3-1.4 MAX 0.025 0.02-0.03 1.2-1.3 0.07-0.1 0.15-0.25 0.02-0.03 MAX 0.25 MAX 0.1 MAX 0.03 0.008-0.012 780.13.2 20MnCr5 138.45 0.17-0.22 0.2-0.35 1.1-1.4 MAX 0.03 0.015-0.035 1-1.3 MAX 0.1 MAX 0.35 0.02-0.05 MAX 0.25 MAX 0.1 MAX 0.02 781.00.1 18CrNiMo7-6 17.997 0.15-0.21 0.2-0.4 0.5-0.6 MAX 0.035 MAX 0.035 1.5-1.8 0.25-0.35 1.4-1.7 0.02-0.1 MAX 0.4 MAX 0.1 MAX 0.03 781.18.1 19CrNiMo7-6 228.75 0.15-0.17 0.2-0.35 0.52-0.62 MAX 0.03 0.018-0.025 1.55-1.65 0.25-0.35 1.42-1.52 0.02-0.03 MAX 0.25 MAX 0.1 MAX 0.03 O3 All the customers' quantities in tons with the delivery date ahead of the deadline. For a proper evaluation of the optimum solution, weights were also used: W1 = 4, W2 = 1 and W3 = 1 for each evaluation part (Oi - number of additional ordered quantity parts, O2 - non-planned cast quantities, and O3 -all the customers' quantities in tons with the delivery date ahead of the deadline). The weights were selected according to the expert scheduler's advice and the preliminary test runs. The respective evaluation function can be simply written as: /e = • O2 + W2 -02 + W3 -03 (1) 6 PARTICLE-SWARM OPTIMIZATION A problem is set in a discrete space, so that the most important task in applying the particle-swarm optimization successfully is to develop effective "problem-mapping" and "solution-generation" mechanisms. If these two mechanisms are devised successfully, it is possible to find good solutions for a given optimization problem in due time. The particle-swarm optimization used can be described in the three following steps14. Let the initialization iterative generation be k = 0, initialization population size psize, and the termination iterative generation Maxgen. Give birth to psize initializing particles. Calculate each particle's fitness value of the initialization population, and let the first generation pi be initialization particles, and choose the particle with the best fitness value of all the particles to be p g (gBest). Every pi,k and pgk crossover can get two child particles, compare them and let the smaller fitness-value particle be the final child of the predecessors. Use equation (2) to obtain the "flying" velocity Vi particles, then utilize equation (3) randomly permuting the N particles of them. Using equations (4) and (5) with the same method gives birth to the next-generation particles Xi. If the fitness value is better than the best fitness value pi (pBest) in history, let the current value be the new pi (pBest). Choose the particle with the best fitness value of all the particles to be pg (gBest). If k = Maxgen, go to Step 3, or else let k = k + 1; go to Step 2. Put out pg. The changing of the particles' velocities is presented with the following equations: vi, k+1 = pi, k ® p g, k (V.1, V.2,..., VrN ) k+1 = P(Vr1, V.2,..., V rN ) (2) (3) (4) (5) P(Vr), P(Xr) refer to the permuting particles Vr and Xr. The termination criterion for the iterations is determined according to the max generation (10 000). For each final work-order schedule 100 independent runs were performed. In the presented algorithm, each particle of the swarm shares mutual information globally and benefits from the discoveries and previous experiences of all the other colleagues during the search process. The algorithm requires only primitive and simple mathematical operators, and is computationally inexpensive in terms of both memory requirements and time. 7 RESULTS OF THE SCHEDULING In order to demonstrate the methodology, real data from the production in October 2009 were used. There were 196 ordered quantities with an average quantity of 21.66 t (standard deviation 37.45 t). Table 6 lists the quality-prescription quantities (46 different quality prescriptions) and their calculated chemical limits for 196 orders. The deadline chosen was 31 October 2009. Table 7: Ordered quantities groups Tabela 7: Skupine naročenih količin (xrl, xr 2,..., XrN ) k +1 = P(Xr1 , Xr 2,..., X rN ) where k represents the iterative generation number, and r (1 = r = psize) is the random integer, which denotes the permuting particle, and # is a crossover denotation denoting the two particles making a crossover operator. Ordered quantities groups # Quality prescriptions within the group Number of customer orders Ordered quantities (tons) 1 108.15.0 2 30.192 2 108.33.0 2 121.5 3 108.70.1 1 18.944 4 127.11.5 14 83.841 5 140.11.1 3 18.038 6 193.31.0 2 18.352 7 193.52.0 4 26.374 8 193.54.0 1 53.872 9 503.14.0 8 4.019 10 503.31.1 7 97.65 11 516.17.1 1 13.616 12 523.00.0 1 46.176 13 524.11.0 1 0.918 14 615.12.0 1 30.251 15 623.32.0 2 218.093 16 625.13.1 2 105.08 17 635.36.5 1 23.088 18 636.11.1 3 515.41 19 705.13.3 2 54.6 20 711.00.1, 711.14.0 3 42.202 21 718.70.2 3 55.388 22 724.24.0 2 38.438 23 732.01.0, 732.03.0, 732.12.5, 732.13.5, 732.18.1, 732.19.1, 732.20.2, 732.21.2, 732.24.4, 732.26.2, 732.27.3, 732.54.2, 732.59.2, 732.62.0, 732.66.0 113 1699.239 24 741.33.3 1 4.144 25 775.13.0 2 25.693 26 779.27.1 1 414.9 27 779.71.4 4 40.848 28 780.10.0, 780.13.2 3 191.25 29 781.00.1, 781.18.1 6 246.747 Table 8: Evaluation parameters of the best organisms in the generations Tabela 8: Parametri ovrednotenja za najboljši organizem generacij Generation # Number of additional ordered quantities parts Non-planned cast quantities (tons) Customer quantities with the delivery date ahead of the deadline (tons) Number of work orders 0 14 36.369 62.881 20 1 13 4.779 95.752 20 2 14 36.369 66.530 20 3 14 0.622 46.909 19 4 14 1.604 45.100 19 5 14 1.604 44.992 19 6 13 1.604 44.913 19 7 13 1.604 44.913 19 8 13 1.604 44.913 19 9 11 1.604 47.144 19 10 11 1.604 47.144 19 11 10 1.604 47.597 19 12 10 1.604 47.597 19 13 10 1.604 47.597 19 14 10 1.604 47.538 19 15 10 1.604 47.197 19 16 10 1.604 47.197 19 17 10 1.604 47.138 19 18 9 10.517 38.294 19 19 9 10.517 38.694 19 20 9 10.517 37.406 19 21 9 10.517 37.406 19 22 9 10.517 37.406 19 23 9 10.517 37.406 19 24 9 10.517 37.258 19 25 9 10.517 37.258 19 26 9 10.517 37.258 19 27 9 10.517 37.230 19 28 9 10.517 37.230 19 29 9 10.517 37.230 19 30 9 10.517 37.230 19 • non-planned cast quantities: 10.517 t • customer quantities with the delivery date ahead of the deadline: 37.230 t • number of work orders: 19. Table 8 shows all the evaluation parameters of the best organisms (the best work-order schedule) in the generations. The best batch-filling schedule was obtained in the 27th generation (generation 0 is a randomly generated generation). For a clearer understanding only the first five successive work orders of the best work-order schedule are presented in the following tables (Tables 9 to 13). Table 9: First work order (out of 19) from the best batch-filling schedule Tabela 9: Prvi delovni nalog (izmed 19) iz najboljšega zaporedja delovnih nalogov Work order number: 0001020 Cover quality prescription code Chemical limitations 732.54.2 / Quality prescription code Customer order code Ordered quantity (tons) Delivery date 732.54.2 901000085507 53 30.10.2009 Table 10: Second work order (out of 19) from the best batch-filling schedule Tabela 10: Drugi delovni nalog (izmed 19) iz najboljšega zaporedja delovnih nalogov From the quality-prescription list (Table 6), 29 ordered quantities groups can be formed (Table 7) on the basis of the instructions defined in section Formation and evaluation of work orders. ln order to make the presentation more clear, let us take a closer look at the batch-filling scheduling of the largest group - group 23. Group 23 presents, in general, the 50CrV4 (W. NR. 1.8159) spring steel. But we must state again that it is not possible to chemically combine all of the quality prescriptions. For instance, we cannot cast, within one batch, the order with the quality prescription 732.66.0 together with 732.12.5 or 732.13.5, or the quality prescription 732.18.1 with 732.59.2 or 732.54.2 (Table 6). In group 23 there are 113 customer orders with the total amount of 1699.239 t, an average ordered quantity of 15.0375 t, and with 52 orders within the deadline. The particle-swarm algorithm scheduled group 23 with the following results: • number of additional ordered quantity parts: 9 Work order number: 0001021 Cover quality prescription code Chemical limitations 732.54.2 wt% C 0.51-0.54! wt% Cr 1.05-1.2! wt% Al 0.015-0.025! Quality prescription code Customer order code Ordered quantity (tons) Delivery date 732.20.2 901000086002 3.148 9.11.2009 732.01.0 901000087902 5.765 8.11.2009 732.54.2 901000085507 44.087 30.10.2009 Table 11: Third work order (out of 19) from the best batch-filling schedule Tabela 11: Tretji delovni nalog (izmed 19) iz najboljšega zaporedja delovnih nalogov Work order number: 0001022 Cover quality prescription code Chemical limitations 732.59.2 wt% Al 0.015-0.04! wt% N MAX 0.012! Quality prescription code Customer order code Ordered quantity (tons) Delivery date 732.01.0 901000093717 16.639 t 31.10.2009 732.20.2 901000087401 5.535 t 31.10.2009 732.01.0 901000093711 5.698 t 31.10.2009 732.01.0 901000093712 11.1 t 31.10.2009 732.20.2 901000086001 5.594 t 31.10.2009 732.62.0 901000094102 6.83 t 31.10.2009 732.59.2 901000084801 1.604 t 2.11.2009 It is possible to notice that the customer order 901000085507 is included in work orders 0001020 (Table 9) and 0001020 (Table 10) - so the order is processed within two batches and thus has an additional part. The best solution is obtained, as mentioned before, when the ordered quantity is cast within one batch. Note: we can see that the optimal batch weight (53 t) of work order 0001023 is not achieved - the non-planned cast quantity is 0.105 t, which is practically insignificant. Such a quantity is usually added to one or more ordered quantities (within 5 % of the ordered quantity). Tabela 12: Četrti delovni nalog (izmed 19) iz najboljšega zaporedja delovnih nalogov Table 12: Fourth work order (out of 19) from the best work-order schedule Work order number: 0001023 Cover quality prescription code Chemical limitations 732.59.2 wt% C 0.51-0.54! wt% P MAX 0.015! wt% Al 0.01-0.025! wt% Sn MAX 0.02! wt% As MAX 0.04! Quality prescription code Customer order code Ordered quantity (tons) Delivery date 732.01.0 901000093718 5.683 t 31.10.2009 732.54.2 901000090501 31.909 t 30.10.2009 732.03.0 901000090401 9.709 t 31.10.2009 732.59.2 901000093101 5.594 t 31.10.2009 732.59.2 Non-planned cast quantity 0.105 t Table 13: Fifth work order (out of 19) from the best work-order schedule Tabela 13: Peti delovni nalog (izmed 19) iz najboljšega zaporedja delovnih nalogov Work order number: 0001024 Cover quality prescription code Chemical limitations 732.54.2 wt% C 0.52-0.54! wt% P MAX 0.015! wt% Sn MAX 0.02! wt% As MAX 0.04! Quality prescription code Customer order code Ordered quantity (tons) Delivery date 732.54.2 9010000873/1 45.028 t 30.10.2009 732.54.2 9010000855/21 3.337 t 30.10.2009 732.24.4 9010000883/10 4.635 t 30.10.2009 The ordered quantities were divided into groups with a similar chemical composition, so that an ordered quantity fits into a group that already includes one or more ordered quantities with a similar chemical composition (similar quality prescriptions). This does not necessary mean that all the orders within a group can be chemically combined. The batches are cast sequentially. The batch-filling schedules were presented as successive ordered quantities. For the evaluation of the work-order schedules, the number of additional ordered quantity parts, non-planned cast quantities in tons and all the customers' quantities with the delivery date ahead of the border-line delivery date were used. For changing the schedules the permutation and the simple one-point crossover operators were used in the particle-swarm algorithm. The batch-filling scheduling strategy has been implemented in Štore Steel Ltd as follows: The period up to 2006: Only the expert knowledge of the batch scheduler was used. The non-planned and ordered quantities with the date ahead of the deadline presented 17.17 % of the total production in 2005. The period after 2006: The particle-swarm algorithm-based search has been used to globally optimize the proper combination of the batches in order to reduce the non-planned and ordered cast quantities with the date ahead of the deadline, and to minimize the number of batches. The non-planned and the ordered quantities with the date ahead of the deadline presented 10.12 % of the total production in 2006 and in 2007. This was enhanced to 16.22 % in 2008, and 32.70 % in 2009. The reasons for the increase lie in the off-standard ordered quantities due to the global economic crisis, and not in the deficiency of the represented algorithm. These quantities would be, of course, much higher in the case of using the expert knowledge only. Acknowledgment The authors would like to thank Mr Jože Vrbovšek for sharing the intellectual territory. The project was funded by Štore Steel Ltd and the Slovenian Research Agency under the grant Programme Group P2-0379 Modelling of Materials and Processes. 8 CONCLUSIONS The present paper deals with improving the batch-filling scheduling by using the particle-swarm method. The scheduling problem was divided into the following subsequent steps: • grouping of the ordered quantities according to their chemical composition, • work-order representation and evaluation, and finally, • particle-swarm algorithm-based search for the optimal batch-filling schedule. 9 REFERENCES 1 J. S. Broughton, M. Mahfouf, D. A. Linkens, A Paradigm for the Scheduling of a Continuous Walking Beam Reheat Furnace Using a Modified Genetic Algorithm, Materials and Manufacturing Processes, 22 (2007), 607-614 2 D. Pacciarelli, M. Pranzo, Production scheduling in a steelmaking-continuous casting plant, Computers and Chemical Engineering, 28 (2004), 2823-2835 3M. Kovacic, B. Šarler, Application of the genetic programming for increasing the soft annealing productivity in steel industry, Materials and Manufacturing Processes, 24 (2009) 3, 369-374 4 B. Verlinden, J. Driver, I. Samajdar, R. D. Doherty, Thermo-mecha-nical Processing of Metallic Materials, 2007, Elsevier, Amsterdam 5 C. Gheorghies, I. Crudu, C. Teletin, C. Spanu, Theoretical Model of Steel Continuous Casting Technology, Journal of Iron and Steel Research, International, 16 (2009) 1, 12-16 6 M. Janik, H. Dyja, Modelling of three-dimensional temperature field inside the mould during continuous casting of steel, Journal of Materials Processing Technology, 157-158 (2004), 177-182 7 B. G. Thomas, F. M. Najjar, Finite element modelling of turbulent fluid flow and heat transfer in continuous casting, Applied Mathematical Modelling, 15 (1991) 5, 226-243 8 L. Wen-hong, X. Zhi, J. Zhen-ping, W. Biao, L. Zhao-yi, J. Guang-lin, Dynamic Water Modeling and Application of Billet Continuous Casting, Journal of Iron and Steel Research, International, 15 (2008) 2, 14-17 9 T. Kolenko, A. Jakli~, J. Lamut, Development of a mathematical model for continuous casting of steel slabs and billets, Mathematical and Computer Modelling of Dynamical Systems: Methods, Tools and Applications in Engineering and Related Sciences, 13 (2007) 1, 1744-5051 10 C. A. Mendez, J. Cerda, I. E. Grossmann, I. Harjunkoski, M. Fahl, State-of-the-art review of optimization methods for short-term scheduling of batch processes, Computers and Chemical Engineering, 30 (2006), 913-946 11 M. Azizoglu, S. Webster, Scheduling a batch processing machine with incompatible job families, Computers & Industrial Engineering, 39 (2001) 3, 325-335 12 L. Tanga, J. Guanb, G. Huc, Steelmaking and refining coordinated scheduling problem with waiting time and transportation consideration, Computers & Industrial Engineering, 58 (2010) 2, 239-248 13 K. Deb, A. R. Reddy, G. Singh, Optimal Scheduling of Casting Sequence Using Genetic Algorithms, Materials and Manufacturing Processes, 18 (2009) 3, 409-432 14 A. Ronga, R. Lahdelmab, Fuzzy chance constrained linear programming model for optimizing the scrap charge in steel production, European Journal of Operational Research, 186 (2008) 3, 953-964 15 L. Zhigang, G. Xingsheng, J. Bin, A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan, Chaos, Solitons and Fractals, 35 (2008) 5, 851-861