(554d) The Unit-Specific General Precedence Scheduling Model: Addressing Sequence-Dependent Setup Times and Costs Issues

Setup times appear often into industrial scheduling problems and are one of the most frequent additional complications in production scheduling. Setup time examples for the process industry are processes such as cleaning of processing units, inspecting of material (analytic and quality control), preheating, mixing and etc. Scheduling problems involving setup times can be mainly categorized in sequence-independent or sequence-dependent setup. Setup is sequence-dependent if its duration depends on both the current and the immediately preceding task, and is sequence-independent if its duration depends only on the current processing task. Sequence-dependent setups scheduling problems constitute the more complicated case.

Some industrial examples of sequence-dependent setups include: (i) chemical compounds manufacturing, where the extent of the cleansing depends on both the chemical most recently processed and the chemical about to be processed and (ii) the printing industry, where the cleaning and setting of the press for processing the next job depend on its difference from the colour of ink, size of paper and types used in the previous job. The case of sequence-dependent setups can be found in numerous other industrial systems, such as the stamping operation in plastic manufacturing, die changing a metal processing shop, and roll slitting in the paper industry. In many cases sequence-dependent setup costs are significant, thus cannot be omitted during the scheduling/planning optimization procedure. It worth mentioning that in some cases could be convenient incorporate process operations into setup times in order to simplify the scheduling model.

Nowadays, the trend in manufacturing of the production of small batches or unit products to satisfy demand and avoid inventory has made more relevant the scheduling problems with sequence-dependent setup times between all jobs, and not only between batches.¹ Despite of the fact that sequence-dependent setups are a reality for the majority of process industries little work has been done towards the development of an efficient scheduling mathematical model addressing the aforementioned aspects. It is pointed out that the consideration of sequence-dependent setups drastically increases the complexity of scheduling models and limits their efficiency and their practical application, since yields to computational expensive mathematical models.

In this work, the unit-specific general precedence (USGP) scheduling MILP model is presented. The concept of the proposed scheduling model has been inspired by the general precedence framework first introduced by Méndez and Cerdá². In the USGP the general precedence concept is applied only for each unit permitting the consideration of sequence-dependent setup times and costs, an issue that the general precedence framework is not able to tackle. The novel USGP framework results into mathematical models that have extremely low computational times for complicated scheduling problems for the already existed scheduling mathematical models. Thus, complex scheduling problems including sequence-dependent setup costs can be solved efficiently. Some case studies are addressed here in order to shed light on the advantages and the special features of the USGP scheduling model. The proposed model efficiently overcomes the deficiencies of the general precedence framework when tackling sequence-dependent setup times and/or costs.

References

[1] Noivo, J. A.; Ramalhinho-Lourenço, H., Solving two production scheduling problems with sequence-dependent set-up times, J. of Economic Literature Classification: C61, M11, L60. 1998.

[2] Méndez, C.; Cerdá, J., Dynamic scheduling in multiproduct batch plants. Comps & Chem. Eng. 2003, 27, 1247?1259.

Acknowledgements

Financial support received from the Spanish Ministry of Education and Science (FPU grants) is fully appreciated. Besides, financial support from PRISM-MRTN-CT-2004-512233 and DPI2006-05673 projects is gratefully acknowledged.