(733c) A New Approach for Scheduling of Operations in Scientific Services Facilities Via Multi-Commodity Flow

Authors: 
Rakovitis, N., University of Manchester
Li, J., The University of Manchester
Zhang, N., University of Manchester
During the past two decades, the short-term scheduling of batch and continuous processes have been extensively discussed. Various models, using different time formulations such as discrete time [1,2], global event point time [3,4], unit-specific event point time [5-7] and time slots [8], as well as different process representations, such as State-task Network [1] (STN) and resource task network (RTN) have been presented. Unit-specific event time formulations are the most efficient of all other formulations as they formulate problems with less variable and constraints and as a result less computational time is required [9]. Their limitation however, is that an iterative procedure is required in order to define the optimal number of events as well as in some cases the total number of events that a task is allowed to span. Additionally, the majority of the proposed models fail to solve medium-term and large-term scheduling problems.

A scientific service facility examines the physical and chemical properties of a great number of samples from different clients. The examination of such properties is done by a number of machines or manpower, which have considerable large capacity and as a result samples from more than one customers can be processed simultaneously. However, in all models presented in the literature, there is the constraint that only one task can be processed in a unit during a specific time slot. Therefore, existing formulations cannot be implemented in order to optimize the scheduling of such facilities. Only recently, Patil et. al [10] and Lagzi et al. [11] presented models for optimizing the scheduling of a scientific services facility. Patil et. al. [10] presented a model based on discrete time formulation. For large-scale problems, they used the rolling horizon technique, where samples that were not able to be processed in the current scheduling horizon, were scheduled to be processed during the next scheduling horizon. Lagzi et al. [11] proposed a model based on global event time formulation for the same problem. The results presented in their work proved that the proposed multitasking formulation proposed is superior than single-tasking models, as a better solution was received. However, the proposed formulation failed to provide an optimal schedule in reasonable amount of time.

In this work, a new model based on unit-specific event time representation, for scheduling of scientific services facilities was proposed. the novelty of this formulation is that an iterative procedure for defining the maximum number of events that a task is allowed to be processed is not required. Instead, it is defined whether it is allowed one task to span in more event point. Furthermore, the proposed model can handle the feature that more than one task can be processed in a unit during a specific time slot. By solving a number of random small, medium and large-scale examples generated for the purpose of this work, the proposed formulation formulates problems with much fewer binary variables and constrains and generates same or better results in significantly less computational time than the global event time formulation of Lagzi et. al. [11].

References

 

[1] Kondili E., Pantelides C. C., Sargent R. W. H. A general algorithm for short-term scheduling of batch operations-I MILP formulation, Computers & Chemical Engineering, 1993;17(2);211-227

[2] Dedopoulos I. T., Shah N., Optimal sort-term scheduling of maintenance and production for multipurpose plants, Industrial and Engineering Chemistry Research, 1995;34(1);192-201

[3] Castro P., Barbosa-Póvoa A. P. F. D., Matos H. An improved RTN continuous-time formulation for the short-term scheduling of multipurpose batch plants, Industrial and Engineering Chemistry research, 2001;40(9);2059-2068

[4] Zhang X., Sargent R., W. H. The optimal operation of mixed production facilities-A general formulation and some approaches for the solution, Computers and Chemical Engineering, 1996;20(6-7);897-904

[5] Ierapetritou M., G. Floudas C., A. Effective continuous-time formulation for short-term scheduling. 1. Multipurpose batch processes, Industrial & Engineering Chemistry, 1998;37(11);4341-4359

[6] Ierapetritou M., G. Floudas C., Effective Continuous-Time Formulation for Short-Term Scheduling 2. Continuous and Semicontinuous Processes, Industrial & Engineering Chemistry, 1998;37(11);4360-4374

[7] Shaik M. A., Floudas C. A. Novel Unified Modeling Approach for Short-Term Scheduling, Industrial & Engineering Chemistry Research, 2009;48(6);2947-2964

[8] Sundaramoorthy A., Karimi I. A. A simpler better slot-based continuous-time formulation for short-term scheduling in multipurpose batch plants, Chemical engineering science, 2005;60(10);2679-2702

[9] Floudas C., A. Lin X. Mixed Integer Linear Programming in Process Scheduling Modeling, Algorithms, and Applications, Annals of operation research, 2005;139(1);131-162

[10] Patil B. P., Fukasawa R., Ricardez-Sandoval L. A. Scheduling of operations in a large-scale Scientific services facility via multicommodity flow and an optimization-based algorithm, Industrial & Engineering Chemistry, 2015;54(5);1628-1639

[11] Lagzi S., Fukasawa R., Ricardez-Sandoval L. A multitasking continuous time formulation for short-term scheduling of operations in multipurpose plants, Computers & Chemical Engineering, 2017;97;135-146