Claims:1. A method for optimizing scheduling of a plant, the method comprising:
defining, by one or more hardware processors, a flow shop scheduling information corresponding to a manufacturing plant, wherein the flow shop scheduling information comprises data on machines, each batch job to be processed, a sequence dependent changeover, and a frequency and a duration of periodic cleaning of each machine (201);
computing, using the defined flow shop scheduling information, an estimated value corresponding to a total number of cleaning-in-place (CIP) processes to be executed on each machine in the process of the flow shop scheduling, wherein the estimated value is computed by implementing an optimized time dependent changeover technique (202);
defining, using the estimated value, one or more constraints corresponding to the defined flow shop scheduling information, wherein the one or more constraints comprise at least one linear parameter and at least one domain for each machine of the flow shop scheduling to be executed for the manufacturing plant (203); and
optimizing, using the one or more constraints, the flow shop scheduling of the manufacturing plant, wherein the optimizing comprises a systematic application of a CIP process in the flow shop scheduling of the manufacturing plant via the optimized time dependent changeover technique (204).

2. The method as claimed in claim 1, wherein the optimized time dependent changeover technique comprises:
(i) implementing, by defining one or more predefined conditions, a first constraint on the flow shop scheduling during a CIP process phase of each machine of the flow shop scheduling, wherein the first constraint eliminates a possibility of processing the batch job during the CIP process phase of each machine, and wherein the first constraint corresponds to the defined one or more constraints;
(ii) implementing, via the one or more hardware processors 104, a second constraint on the flow shop scheduling, wherein the second constraint comprises executing an initial CIP process phase after an execution of a first batch job in the flow shop scheduling and further sequencing of the subsequent CIP process phases, and wherein the second constraint corresponds to the defined one or more constraints; and
(iii) implementing, by the optimized time dependent changeover technique, a third constraint on the flow shop scheduling, wherein the third constraint comprises utilizing at least one batch job between two CIP processes of each machine of the flow shop scheduling, and wherein the third constraint corresponds to the defined one or more constraints.

3. The method as claimed in claim 1, wherein the estimated value is computed as a ratio of a maximum executing time of a machine in the process of the flow shop scheduling and a maximum time the machine is executed without a CIP process phase.

4. The method as claimed in claim 1, wherein at least one constraint amongst the defined one or more constraints facilitate defining a sequence of the flow shop scheduling for the systematic application of the CIP process.

5. The method as claimed in claim 1, wherein the step of optimizing is preceded by defining, based upon the defined one or more constraints, a maximum duration between two CIP processes to be executed for each machine of the flow shop scheduling.

6. The method as claimed in claim 2, wherein the third constraint is terminated, using a predefined binary variable, upon determining an execution of each batch job on a machine in the flow shop scheduling.

7. The method as claimed in claim 1, wherein the one or more constraints comprises a minimum starting point constraint for computing a minimum starting time of execution of a machine in the flow shop scheduling, and wherein the computed minimum starting time facilitates the systematic application of the CIP process.

8. A system (100) for optimizing scheduling of a plant, the system (100) comprising:
a memory (102) storing instructions;
one or more communication interfaces (106); and
one or more hardware processors (104) coupled to the memory (102) via the one or more communication interfaces (106), wherein the one or more hardware processors (104) are configured by the instructions to:
define a flow shop scheduling information corresponding to a manufacturing plant, wherein the flow shop scheduling information comprises data on machines, each batch job to be processed, a sequence dependent changeover and a frequency, and a duration of periodic cleaning of each machine;
compute, using the defined flow shop scheduling information, an estimated value corresponding to a total number of cleaning-in-place (CIP) processes to be executed on each machine in the process of the flow shop scheduling, wherein the estimated value is computed by implementing an optimized time dependent changeover technique;
define, using the estimated value, one or more constraints corresponding to the defined flow shop scheduling information, wherein the one or more constraints comprise at least one linear parameter and at least one domain for each machine of the flow shop scheduling to be executed for the manufacturing plant; and
optimize, using the one or more constraints, the flow shop scheduling of the manufacturing plant, wherein the optimizing comprises a systematic application of a CIP process in the flow shop scheduling of the manufacturing plant via the optimized time dependent changeover technique.

9. The system (100) as claimed in claim 8, wherein the optimized time dependent changeover technique comprises:
(i) implement, by defining one or more predefined conditions, a first constraint on the flow shop scheduling during a CIP process phase of each machine of the flow shop scheduling, wherein the first constraint comprises eliminating a possibility of processing the batch job during the CIP process phase of each machine, and wherein the first constraint corresponds to the defined one or more constraints;
(ii) implement, via the one or more hardware processors 104, a second constraint on the flow shop scheduling, wherein the second constraint comprises executing an initial CIP process phase after an execution of a first batch job in the flow shop scheduling and further sequencing of the subsequent CIP process phases, and wherein the second constraint corresponds to the defined one or more constraints; and
(iii) implement, by the optimized time dependent changeover technique, a third constraint on the flow shop scheduling, wherein the third constraint comprises processing at least one batch job between two CIP processes of each machine of the flow shop scheduling, and wherein the third constraint corresponds to the defined one or more constraints.

10. The system (100) as claimed in claim 8, wherein the one or more hardware processors (104) are configured to compute the estimated value as a ratio of a maximum executing time of a machine in the process of flow shop scheduling and a maximum time the machine is executed without a CIP process phase.

11. The system (100) as claimed in claim 8, wherein the one or more hardware processors (104) are configured to define a sequence of the flow shop scheduling for the systematic application of the CIP process.

12. The system (100) as claimed in claim 8, wherein the one or more hardware processors (104) are configured to define, based upon the one or more constraints, a maximum duration between two CIP processes to be executed for each machine of the flow shop scheduling.

13. The system (100) as claimed in claim 9, wherein the one or more hardware processors (104) are configured to terminate the third constraint using a predefined binary variable upon determining an execution of each batch job on a machine in the flow shop scheduling.

14. The system (100) as claimed in claim 8, wherein the one or more constraints comprises a minimum starting point constraint for computing a minimum starting time of execution of a machine in the flow shop scheduling, and wherein the computed minimum starting time facilitates the systematic application of the CIP process.
, Description:FORM 2

THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003

COMPLETE SPECIFICATION
(See Section 10 and Rule 13)

Title of invention:

SYSTEMS AND METHODS FOR OPTIMIZING SCHEDULING OF A PLANT

Applicant

Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman point, Mumbai 400021,
Maharashtra, India

The following specification particularly describes the invention and the manner in which it is to be performed.


TECHNICAL FIELD
The disclosure herein generally relates to plant scheduling, and, more particularly, to systems and methods for optimizing scheduling of a plant.

BACKGROUND
A production schedule used by a manufacturing plant plays a critical role in daily operation. In most manufacturing plants, when a multitude of different orders need to be fulfilled to satisfy a variety of customer applications, a need arises to manufacture the products with minimum time delay and maintaining at the same time, full utilization of the production resources. While traditional techniques implementing linear programming methodologies have been used to solve the problems like scheduling optimization and allocation of limited resources amongst competitive activities, the traditional techniques require technical advancement to handle scenarios when production equipment dynamically changes and poses operational constraints due to the nature of the equipment.
In assembly lines of many manufacturing companies, there are a number of operations that have to be performed on every job. Frequently, these jobs can follow the same route in assembly line meaning that the processing order of the jobs on machines should remain the same. The machines are normally set up in series, which constitute a flow-shop, and the scheduling of the jobs in this environment is commonly referred to as flow-shop scheduling. An apparent example for such a shop is an assembly line, where the workers (or workstations) represent the machines and a unidirectional conveyer performs the materials handling for machines. In this particular example, operations are performed on materials. A job in the aforementioned environment is accomplished the moment the material of interest leaves the last machine.

SUMMARY
Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. For example, in one embodiment, a method for optimizing scheduling of a plant, the method comprising: defining, by one or more hardware processors, a flow shop scheduling information corresponding to a manufacturing plant, wherein the flow shop scheduling information comprises data on machines, each batch job to be processed, a sequence dependent changeover, and a frequency and a duration of periodic cleaning of each machine ; computing, using the defined flow shop scheduling information, an estimated value corresponding to a total number of cleaning-in-place (CIP) processes to be executed on each machine in the process of the flow shop scheduling, wherein the estimated value is computed by implementing an optimized time dependent changeover technique; defining, using the estimated value, one or more constraints corresponding to the defined flow shop scheduling information, wherein the one or more constraints comprise at least one linear parameter and at least one domain for each machine of the flow shop scheduling to be executed for the manufacturing plant; optimizing, using the one or more constraints, the flow shop scheduling of the manufacturing plant, wherein the optimizing comprises a systematic application of a CIP process in the flow shop scheduling of the manufacturing plant via the optimized time dependent changeover technique; implementing, by defining one or more predefined conditions, a first constraint on the flow shop scheduling during a CIP process phase of each machine of the flow shop scheduling, wherein the first constraint eliminates a possibility of processing the batch job during the CIP process phase of each machine, and wherein the first constraint corresponds to the defined one or more constraints; implementing, via the one or more hardware processors 104, a second constraint on the flow shop scheduling, wherein the second constraint comprises executing an initial CIP phase after an execution of a first batch job in the flow shop scheduling and further sequencing of the subsequent CIP process phases, and wherein the second constraint corresponds to the defined one or more constraints; implementing, by the optimized time dependent changeover technique, a third constraint on the flow shop scheduling, wherein the third constraint comprises utilizing at least one batch job between two CIP processes of each machine of the flow shop scheduling, and wherein the third constraint corresponds to the defined one or more constraint; and defining, based upon the defined one or more constraints, a maximum duration between two CIP processes to be executed for each machine of the flow shop scheduling.
In another aspect, there is provided a system for optimizing scheduling of a plant, the system comprising a memory storing instructions; one or more communication interfaces; and one or more hardware processors coupled to the memory via the one or more communication interfaces, wherein the one or more hardware processors are configured by the instructions to: define a flow shop scheduling information corresponding to a manufacturing plant, wherein the flow shop scheduling information comprises data on machines, each batch job to be processed, a sequence dependent changeover and a frequency, and a duration of periodic cleaning of each machine; compute, using the defined flow shop scheduling information, an estimated value corresponding to a total number of cleaning-in-place (CIP) processes to be executed on each machine in the process of the flow shop scheduling, wherein the estimated value is computed by implementing an optimized time dependent changeover technique; define, using the estimated value, one or more constraints corresponding to the defined flow shop scheduling information, wherein the one or more constraints comprise at least one linear parameter and at least one domain for each machine of the flow shop scheduling to be executed for the manufacturing plant; and optimize, using the one or more constraints, the flow shop scheduling of the manufacturing plant, wherein the optimizing comprises a systematic application of a CIP process in the flow shop scheduling of the manufacturing plant via the optimized time dependent changeover technique; implement, by defining one or more predefined conditions, a first constraint on the flow shop scheduling during a CIP process phase of each machine of the flow shop scheduling, wherein the first constraint comprises eliminating a possibility of processing the batch job during the CIP process phase of each machine, and wherein the first constraint corresponds to the defined one or more constraints; implement a second constraint on the flow shop scheduling, wherein the second constraint comprises executing an initial CIP phase after an execution of a first batch job in the flow shop scheduling and further sequencing of the subsequent CIP process phases, and wherein the second constraint corresponds to the defined one or more constraints; and implement, by the optimized time dependent changeover technique, a third constraint on the flow shop scheduling, wherein the third constraint comprises processing at least one batch job between two CIP processes of each machine of the flow shop scheduling, and wherein the third constraint corresponds to the defined one or more constraints; and define, based upon the defined one or more constraints, a maximum duration between two CIP processes to be executed for each machine of the flow shop scheduling.
In yet another aspect, there is provided one or more non-transitory machine readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors causes the one or more hardware processors to perform a method for for optimizing scheduling of a plant, the method comprising: defining, by one or more hardware processors, a flow shop scheduling information corresponding to a manufacturing plant, wherein the flow shop scheduling information comprises data on machines, each batch job to be processed, a sequence dependent changeover, and a frequency and a duration of periodic cleaning of each machine ; computing, using the defined flow shop scheduling information, an estimated value corresponding to a total number of cleaning-in-place (CIP) processes to be executed on each machine in the process of the flow shop scheduling, wherein the estimated value is computed by implementing an optimized time dependent changeover technique; defining, using the estimated value, one or more constraints corresponding to the defined flow shop scheduling information, wherein the one or more constraints comprise at least one linear parameter and at least one domain for each machine of the flow shop scheduling to be executed for the manufacturing plant; optimizing, using the one or more constraints, the flow shop scheduling of the manufacturing plant, wherein the optimizing comprises a systematic application of a CIP process in the flow shop scheduling of the manufacturing plant via the optimized time dependent changeover technique; implementing, by defining one or more predefined conditions, a first constraint on the flow shop scheduling during a CIP process phase of each machine of the flow shop scheduling, wherein the first constraint eliminates a possibility of processing the batch job during the CIP process phase of each machine, and wherein the first constraint corresponds to the defined one or more constraints; implementing, via the one or more hardware processors 104, a second constraint on the flow shop scheduling, wherein the second constraint comprises executing an initial CIP process phase after an execution of a first batch job in the flow shop scheduling and further sequencing of the subsequent CIP process phases, and wherein the second constraint corresponds to the defined one or more constraints; implementing, by the optimized time dependent changeover technique, a third constraint on the flow shop scheduling, wherein the third constraint comprises utilizing at least one batch job between two CIP processes of each machine of the flow shop scheduling, and wherein the third constraint corresponds to the defined one or more constraint; and defining, based upon the defined one or more constraints, a maximum duration between two CIP processes to be executed for each machine of the flow shop scheduling.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.

BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed principles.
FIG. 1 illustrates block diagram of a system for optimizing scheduling of a plant, in accordance with some embodiments of the present disclosure.
FIG. 2 is a flow diagram illustrating the steps involved in the process of for optimizing scheduling of the plant, in accordance with some embodiments of the present disclosure.
FIG. 3 an example of a flow shop scheduling information for optimizing scheduling of the plant, in accordance with some embodiments of the present disclosure.
FIG. 4 illustrates graphically an obtained optimum flow shop schedule, wherein the obtained optimum flow shop schedule depicts starting and completion times of each job on each machine, in accordance with some embodiments of the present disclosure.

DETAILED DESCRIPTION OF EMBODIMENTS
Exemplary embodiments are described with reference to the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are possible without departing from the spirit and scope of the disclosed embodiments. It is intended that the following detailed description be considered as exemplary only, with the true scope and spirit being indicated by the following claims.
Embodiments of the present disclosure provide systems and methods for optimizing scheduling of a plant. In a flow shop scheduling model, each job must be processed on a set of machines in identical order. The goal is to determine the job sequence to optimize a certain predetermined objective function. At any given time, each machine can process at most one job. Meanwhile, a job cannot be preempted by the other jobs. Flow shop scheduling problems widely exist in industrial production and mechanical manufacturing.
For example, in a steel-making process, molten steel is casted into semi-finished slabs by a conticaster, after being heated by the heat furnace, the slabs are rolled into products in rolling mill. Obviously, it is a typical flow shop production model. As most of the flow shop scheduling techniques impose a large number of restrictive assumptions, it is impossible to obtain the global optimum solution in polynomial time. Hence, the study of flow shop scheduling algorithms is very important for reducing running time and boosting productivity.
The traditional systems and methods implementing the flow shop scheduling techniques suffer from various limitations. For example, the traditional systems and methods model time dependent changeover technique(s) in flow shop batch plants with restrictive assumptions. For example, some of the traditional systems and methods restrict cleaning-in-place (CIP) process arising due to a time dependent changeover to a time window specified by a user. The method disclosed attempts to overcome the limitations of the traditional system and methods. For example, the method disclosed provides for optimizing schedule of a batch flow shop by setting the cleaning times of the CIP process arising due to the time dependent changeover to be free while stating the process in intuitive and native format.
Referring now to the drawings, and more particularly to FIG. 1 through 4, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and/or method.
FIG. 1 illustrates an exemplary block diagram of a system 100 for optimizing scheduling of a plant, in accordance with an embodiment of the present disclosure. In an embodiment, the system 100 includes one or more processors 104, communication interface device(s) or input/output (I/O) interface(s) 106, and one or more data storage devices or memory 102 operatively coupled to the one or more processors 104. The one or more processors 104 that are hardware processors can be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor(s) is configured to fetch and execute computer-readable instructions stored in the memory 102. In an embodiment, the system 100 can be implemented in a variety of computing systems, such as laptop computers, notebooks, hand-held devices, workstations, mainframe computers, servers, a network cloud and the like.
The I/O interface device(s) 106 can include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and the like and can facilitate multiple communications within a wide variety of networks N/W and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. In an embodiment, the I/O interface device(s) can include one or more ports for connecting a number of devices to one another or to another server. The system 100, through the I/O interface 106 may be coupled to external data sources.
The memory 102 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. In an embodiment, the memory 102 can be configured to store any data that is associated with optimizing the scheduling of the plant. In an embodiment, the information pertaining to each batch job to be processed, number of machines for processing each batch job and processing time for each batch constraints corresponding to flow shop scheduling information job etc. is stored in the memory 102. Further, all information (inputs, outputs and so on) pertaining to optimizing the scheduling of the plant, may also be stored in the database, as history data, for reference purpose.
FIG. 2, with reference to FIG. 1, illustrates an exemplary flow diagram of a method for optimizing the scheduling of the plant, in accordance with some embodiments of the present disclosure. In an embodiment the system 100 comprises one or more data storage devices of the memory 102 operatively coupled to the one or more hardware processors 104 and is configured to store instructions for execution of steps of the method by the one or more processors 104. The steps of the method of the present disclosure will now be explained with reference to the components of the system 100 as depicted in FIG. 1 and the flow diagram. In the embodiments of the present disclosure, the hardware processors 104 when configured the instructions performs one or more methodologies described herein.
According to an embodiment of the present disclosure, at step 201, the one or more hardware processors 104 are configured to define a flow shop scheduling information corresponding to a manufacturing plant. Generally, in flow shop scheduling there are n machines (or stages) and m jobs (or products). Each job has to be processed by exactly n operations (to be performed in one or more machines) and the i^th operation of a job has to be executed on i^th machine. A machine cannot process more than one job at a time. Processing of all the jobs has to be done in the same order, that is, a first process on a first machine, a second machine on a second stage and the like.
Further, the processing time for each job in every machine is given. Jobs may be processed in any order but it is generally assumed that the order is same for each machine. Also, an intermediate cleaning may be required between processing of different jobs on a machine, and the duration of cleaning may depend on the sequence in which the jobs are processed. This is called as a sequence dependent changeover. Also, the condition of each machine deteriorates as it processes one job after another. Thus, cleaning / changeover of a machine may be required after every fixed interval of time. This is called as a time dependent changeover.
The changeovers are usually carried out without disassembling the machines and hence is called as a Cleaning-In-Place (CIP) process. The optimization formulation finds the order in which the jobs need to be processed for maximum performance considering both the sequence dependent changeover and the time dependent changeover (CIP). The CIP process mentioned hereinafter shall be with respect to time dependent changeover. The performance indicator commonly used comprises the makespan or the total time required to finish manufacturing all the jobs. Generally, it is the goal of scheduling optimization to minimize the makespan by deciding the order in which the jobs need to be processed and, start and end times of each operation on every machine taking into account various changeovers.
Considering an example scenario, by referring to FIG. 3, an example of the flow shop scheduling information for a product, comprising a layout of the process to be executed, is defined, wherein the layout comprises executing cutting operations, followed by welding operations and finally packing operations. Further, there are six jobs which need to be processed, that is, a chair, a chest, a door, a table, a shelf, and a drawer. The processing times of each job in the machine is provided along with the details of the time dependent changeover and the sequence dependent changeover may be defined as shown in Tables 1 through 6 below, wherein Table 2 provides the processing times (procT_(i,j)) of various jobs in all the machines, Tables 3, 4 and 5 shows a changeover time (clean_(i,i^',j)) for all the combinations of jobs for cutting, welding and packing machines respectively, and Table 1 depicts remaining data for the flow shop scheduling information for a product.
To formulate an optimization problem, a set of parameters may be specified. The information required to formulate the problem may be referred to in the Table 1 below:
Table 1
Parameter Description Value
jobs Set of jobs to be processed {chest,chair,door,table,
shelf,drawer}
jobs_j^ZW Set of jobs having zero-wait condition between machines j and j+1 -
machines Set of machines used in the manufacturing process {cutting,welding,packing}
jobs_N Number of jobs 6
machines_N Number of machines 3
procT_(i,j) Time required to process a job i in machine j Refer Table 2
cleanT_(i,i',j) Time required to clean a machine if a job i is processed after i' in said machine (Sequence dependent changeover) Refer Tables 3,4 and 5
duration_j^cip Duration of time dependent changeover (CIP) for machine j 8
interval_j^cip Frequency of time dependent changeover or periodic cleaning (CIP) 60
weight Weight to be used in the Objective function 1000
M Scheduling horizon 1000

Table 2
j 1 2 3
i Cutting Welding Packing
Chest 25 25 30
Door 20 25 25
Chair 30 20 15
Table 30 25 25
Shelf 25 25 15
Drawer 25 30 25
Table 3
Chest Door Chair Table Shelf Drawer
Chest 0 3 5 3 2 1
Door 5 0 6 4 2 1
Chair 2 3 0 2 2 1
Table 2 5 3 0 2 1
Shelf 2 5 3 2 0 1
Drawer 2 5 3 2 1 0

Table 4
Chest Door Chair Table Shelf Drawer
Chest 0 3 5 3 2 1
Door 5 0 6 4 2 1
Chair 2 3 0 2 2 1
Table 2 5 3 0 2 1
Shelf 2 5 3 2 0 1
Drawer 2 5 3 2 1 0

Table 5
Chest Door Chair Table Shelf Drawer
Chest 0 3 5 3 2 1
Door 5 0 6 4 2 1
Chair 2 3 0 2 2 1
Table 2 5 3 0 2 1
Shelf 2 5 3 2 0 1
Drawer 2 5 3 2 1 0

According to an embodiment of the present disclosure, at step 202, the one or more hardware processors 104 are configured to compute, using the defined flow shop scheduling information, an estimated value corresponding to a maximum number of cleaning-in-place (CIP) processes to be executed in the process of the flow shop scheduling, wherein each CIP process amongst the maximum number of CIP processes arise due to the time dependent changeover. The method disclosed provides for computing the estimated value by implementing an optimized time dependent changeover technique. The process of computing the estimated value via the optimized time dependent changeover technique may be considered in detail by initially elaborating and understanding the optimized time dependent changeover technique.
Optimized time dependent changeover technique – The optimized time dependent technique may be elaborated / implemented in four steps:
Eliminating a possibility of utilization of a machine during CIP process– In an embodiment, the one or more hardware processors 104 implement, by defining one or more predefined conditions, a first constraint on the flow shop scheduling during a CIP process phase of each machine of the flow shop scheduling, wherein the first constraint eliminates (or forbids) a possibility of processing of the batch job during the CIP process phase on each machine, and wherein the first constraint corresponds to defined one or more constraints. When a CIP process is encountered for a machine (say from time T to time T+duration_j^cip), no job may start or finish processing in that machine from time T to time T+duration_j^cip. Thus, a decision has to be made regarding processing of a job either before or after a CIP phase.
Deciding CIP times – According to an embodiment of the present disclosure, the one or more hardware processors 104 implement a second constraint on the flow shop scheduling, wherein the second constraint decides the CIP process start times based on the time dependent changeover requirement in the flow shop scheduling, and wherein the second constraint corresponds to the defined one or more constraints. The second constraint enforces the execution of an initial CIP process phase only after an execution of a first batch job in a machine. The initial CIP process of a machine must start before a duration of i?nterval?_j^cip after starting to process the first job in a machine. To implement this, the time at which it started processing the first job must be computed. The subsequent CIP process phases should start within the duration of interval_j after completion of previous CIP process phase. Thus, the mentioned technique must use multiple reference points to implement CIP process arising due to time dependent changeover.
Ensuring utilization of a machine between two CIP processes– According to an embodiment of the present disclosure, the one or more hardware processors 104 implement a third constraint on the flow shop scheduling, wherein the third constraint ensures that a machine is utilized between two CIP processes of the flow shop scheduling, and wherein the third constraint corresponds to the defined one or more constraints. Since the proposed methodology provides for defining the maximum number of CIP processes to be executed by a user, the requirement of ensuring at least one job is processed between two CIP processes must be terminated once all the jobs are processed in a machine.
Computing N_cip – N_cip is the total number of CIP processes that are required to be carried out on each machine in the process of flow shop scheduling. The parameter Ncip may have a significant effect on the size of a flow shop scheduling model. It may result in non-realistic solutions if set too low, and if given too high, may lead to unnecessary use of a computing power.
To estimate a reasonable value of Ncip (referred as the estimated value) so that the size of the model is tractable and to obtain a physically realizable solution, the proposed disclosure provides for a heuristic technique to find a reasonable value. In the worst case, it may be required to do cleaning of a machine after processing every job in it. Thus, jobs_N is the upper bound of N_cip.
Ncip may be decided based on the amount of time a machine is processing the batches. The intermediate cleaning, that is, the sequence dependent changeover may also be considered as a time of utilization for a machine, as it is not a substitute of the CIP process. Thus, based on the above mentioned steps, the estimated maximum running time of a machine is equal to or less than the sum of processing times for all the jobs plus the largest jobs_N-1 sequence dependent changeover times for that machine. The estimated value of the number of cleaning-in-place (CIP) process required for a machine may be computed as a ratio of estimated maximum running time of a machine of the flow shop scheduling and a maximum time the machine is executed without a CIP phase (interval_j^cip ). This estimated number of CIP processes is calculated for every machine and the maximum of the integral part of the value is assigned to N_cip, which is the total number of cleanings to be executed on each machine.
Further, in the formulation of the optimization problem, the components may be the variables used. The list of variables to be used may be referred to in Table 6 below:
Table 6
Variable Description
startT_(i,j) Time at which a job i is started processing in machine j
cipT_(j,n) Time at which n^th cleaning-in-place (CIP) process starts in machine j
prec_(i,i^' ) Binary variable deciding the precedence of two jobs i and i' (i? i')
cip_j^start Reference point for initial CIP process for machine j
makespan Time at which all the products are finished processing. It is equal to the completion time of the last job processed in last machine
cip_dist Sum of the difference between startT_(i,j) and cip_j^start. Used to equate cip_j^start to minimum of startT_(i,j) using only linear constraints and objective
afterCIP_(i,j,n) Binary variable deciding whether a product i is processed in machine j after n^th CIP process (=1) or not (=0)
k_(j,n) Binary variable enforcing processing of at least one job between n^th and (n+1)^th CIP process

According to an embodiment of the present disclosure, at step 203, the one or more hardware processors 104 are configured to define one or more constraints corresponding to the defined flow shop scheduling information using the estimated value. The one or more constraints comprise at least one linear parameter and at least one domain for each machine of the flow shop scheduling to be executed for the manufacturing plant. Since the objective of the flow shop scheduling is to minimize the makespan, there is required a set of rules for a systematic application of a cleaning-in-place (CIP) process arising due to the time dependent changeover. The one or more constraints thus facilitate the systematic application of the CIP process. The one or more constraints may be defined as shown in Table 7 below:
Table 7
Serial Number Constraint Domain
1 startT_(i',j)=startT_(i,j)+procT_(i,j)+cleanT_(i?,i?^',j)-M(1-prec_(ii^' )) ?i,i^'?jobs,i?i^',j?{1,2,3,..,?machines?_N}
2 startT_(i,j)=startT_(i^',j)+procT_(i^',j)+cleanT_(i^',i,j)-M(prec_(ii^' )) ?i,i^'?jobs,i?i^',j?{1,2,3,..,?machines?_N}
3 makespan=startT_(i,J)+procT_(i,J) ?i?jobs,J=machines_N
4 startT_(i,j+1)=startT_(i,j)+procT_(i,j) ?i?(jobs-jobs^ZW ),j?{1,2,3,…,machines_N-1}

5 startT_(i,j+1)=startT_(i,j)+procT_(i,j) ?i?jobs^ZW,j?{1,2,3,…,machines_N-1}

6 cip_dist=?_(j?machines)¦?_(i?jobs)¦?startT_(i,j)-cip_j^start ? NA
7 cip_j^start=startT_(i,j) ?i?jobs,
j?{1,2,3,…,machines_N}
8 ?_(i?jobs)¦?(afterCIP_(i,j,1) )+1=? jobs_N ?j?{1,2,3,…,machines_N}
9 cip_j^start=cipT_(j,1)=cip_j^start+interval_j^cip ?j?{1,2,3,…,machines_N}
10 cipT_(j,n+1)-cipT_(j,n)=interval_j^cip+duration_j^cip ?j?{1,2,3,…,machines_N},
n?{1,2,3,…,N_cip-1}
11 cipT_(j,n+1)=cipT_(j,n)
12 startT_(i,j)=cipT_(j,n)+duration_j^cip-M(1-afterCIP_(i,j,n)) ?i?jobs,j?{1,2,3,…,machines_N},n?{1,2,3,…,N_cip-1}

13 startT_(i,j)+procT_(i,j)=cipT_(j,n)+M(afterCIP_(i,j,n))
14 (?_(i?jobs)¦(1-afterCIP_(i,j,n) ) )+1= (?_(i?jobs)¦(1-afterCIP_(i,j,n+1) ) )+M(1-k_(j,n)) ?j?{1,2,3,…,machines_N },
n?{1,2,3,…,N_cip-1}
15 M×k_(j,n)=2×jobs_N-(?_(i?jobs)¦(1-afterCIP_(i,j,n) ) +?_(i?jobs)¦(1-afterCIP_(i,j,n+1) ) )
16 k_(j,n)=2×jobs_N-(?_(i?jobs)¦(1-afterCIP_(i,j,n) ) +?_(i?jobs)¦(1-afterCIP_(i,j,n+1) ) )

According to an embodiment of the present disclosure, the function of each constraint (that is, constraint 1 to 16 defined in Table 7 supra gain) may now be discussed in detail. By referring to Table 7 supra yet again, constraints (1) and (2) ensure that a machine is utilised by at most one job at given time. Constraints (1) and (2) also ensure that a job is not processed unless intermediate cleaning (the sequence dependent changeover) is done, if required. If prec_(i,i^' ) is 1 (i.e. if i' follows i), constraint (2) becomes redundant and constraint (1) governs the solution. This ensures that i' is started processing by j only after i is processed and intermediate cleaning is done. If prec_(i,i^' ) is 0 (i.e. if i follows i'), then the constraint (1) is turned redundant, implying i is started processing by j only after i' is processed and intermediate cleaning is done.
By referring to Table 7 yet again, constraint (3) sets the makespan to be greater than completion time of all jobs in last machine. Constraints (4) and (5) define the sequence of the flow shop scheduling, thereby ensuring that a job is processed in machine j before being processed in j+1.
Constraint (5) enforces a condition that jobs having zero wait policy between machines j and j+1 are started processing in j+1 as soon as they are finished processing in j. For a flow shop scheduling with no time dependent changeovers or CIP process, constraints (1) to (5), may be enough to find the optimum solution. By referring to Table 7 yet again, constraints (6) and (7) are minimum starting time constraints. To incorporate time dependent changeover, a minimum of startT_(i,j) for a given machine j is to be computed, to ensure that an equipment is not utilised for more than interval_j^cip units of time without a CIP process phase. This acts as reference point for initial CIP process phase.
In an embodiment, constraints (6) and (7) and the corresponding objective (discussed in subsequent paragraphs) facilitate computing of the minimum of starting times in each machine or machine and store them in cip_j^start. To find the minimum starting time, the one or more hardware processors 104 compute cip_dist as sum of difference of startT_(i,j) and cip_j^start for all jobs and machines (refer (6)). Further, constraint (7) ensures that cip_dist is a sum of non-negative values.
By referring to Table 7 yet again, constraints (8) and (9) defined implements that the first CIP process starts only after first job is processed in a given machine, but before the utilization time for a given equipment exceeds interval_j^cip. Further, constraint (10) ensures that maximum gap between two CIP processes is less than or equal to the maximum running time allowed for an equipment without cleaning. Thus, the reference time for the first CIP is the start of processing of the first product (cip_j^start) and for the subsequent CIP, processes the reference is the completion time of the previous CIP process. Hence, constraint (10) defines a maximum duration between two CIP processes to be executed for each machine in the process of flow shop scheduling. The one or more hardware processors 104, via constraint (11) sequence the CIP processes such that n^th cleaning happens before the (n+1)^th cleaning.
According to an embodiment of the present disclosure, constraints (12) and (13) ensure that when the CIP process of a machine is taking place, no job can be started or finished processing in it. If a process starts after n^th CIP process (that is, if after CIP_(i,j,n) = 1), then, startT_(i,j) is greater than cipT_(j,n)+duration_j^cip. This is implied by turning the constraint (13) redundant. On the other hand, if a process starts before n^th CIP process (i.e. if afterCIP_(i,j,n) = 0), constraint (12) becomes redundant, thereby ensuring that the job is finished processing before the CIP process takes place. Constraint (14) ensures that at least one job is processed on a machine between two CIP processes unless all the jobs are processed on that machine.
Finally, constraints (15) and (16) implements a check that k_(j,n) needs to be 0 if there are no jobs left to be processed between cipT_(j,n) and cipT_(j,n+1). If 2×jobs_N-(?_(i?jobs)¦(1-afterCIP_(i,j,n) ) +?_(i?jobs)¦(1-afterCIP_(i,j,n+1) ) ) is non-zero, kj,n has to be 1 (enforced by constraint (15)). In such a case constraint, (16) may also be satisfied. If 2×jobs_N-(?_(i?jobs)¦(1-afterCIP_(i,j,n) ) +?_(i?jobs)¦(1-afterCIP_(i,j,n+1) ) ) becomes 0, then k_(j,n) is forced to be 0 by (16). Thus, the variable k_(j,n) is zero when there is no job left to be processed between n^th and (n+1)^th CIP process. Otherwise it assumes the value of 1.
According to an embodiment of the present disclosure, at step 204, the one or more hardware processors 104 are configured to optimize, using the one or more constraints, the flow shop scheduling of the manufacturing plant. The optimizing comprises the systematic application of a CIP process in the flow shop scheduling of the manufacturing plant via the optimized time dependent changeover technique. The systematic application of the CIP process is executed in four steps via the optimized time dependent changeover technique as discussed in step 203 above. The systematic application of the CIP process by using the estimated value may now be discussed in detail by implementing and executing the optimized time dependent changeover technique in the flow shop scheduling information defined in step 201.
The implementation of the method disclosed (that is, steps 201 through 204) to solve the problem of flow shop scheduling discussed in step 201 may now be discussed in detail. As mentioned in step 201 supra, the layout comprises executing cutting operations, followed by welding operations and finally, packing operations. Further, there are six jobs which need to be processed, that is, a chair, a chest, a door, a table, a shelf and a drawer. The processing times of each job in the machine is provided along with the details of the time dependent changeover may be defined as shown in Tables 1 through 5 supra.
Initially, the one or more hardware processors 104 perform the computation of N_cip from the defined flow shop scheduling in step 201 as:
Computation of N_cip for machine cutting:
Sum of processing times of all jobs = 25+20+30+30+25+25 = 155 minutes (from Table 1);
Sum of largest 5 (jobs_N-1=6-1) sequence dependent changeover = 5+5+6+5+5 = 26 minutes (From Table 3)
Maximum running time of machine = 155 + 26 minutes = 181 minutes;
Ratio of maximum running time of machine to interval_j^cip = 181 ÷ 60 = 3.02; and
Thus 3 (integer part of 3.02) CIP processes are required for this machine.
Computation of N_cip for machine welding:
Sum of processing times of all jobs = 25+25+20+25+25+30 = 150 minutes (From Table 1);
Sum of largest 5 (jobs_N-1=6-1) sequence dependent changeover = 5+5+6+5+5 = 26 minutes (From Table 4);
Maximum running time of machine = 150 + 26 minutes = 176 minutes;
Ratio of maximum running time of machine to interval_j^cip = 176 ÷ 60 = 2.93; and
Thus 2 (integer part of 2.93) CIP processes are required for this machine.
Computation of N_cip for machine packing –
Sum of processing times of all jobs = 30+25+15+25+15+25 = 135 minutes (From Table 1);
Sum of largest 5 (jobs_N-1=6-1) sequence dependent changeover = 5+5+6+5+5 = 26 minutes (From Table 5);
Maximum running time of machine = 135 + 26 minutes = 161 minutes;
Ratio of maximum running time of machine to interval_j^cip = 161 ÷ 60 = 2.68;
Thus 2 (integer part of 2.68) CIP processes are required for this machine and, N_cip=max?{3,2,2}=3; and
If N_cip was set to its upper bound which is 6 (total number of jobs), it may result in increasing the size of the problem unnecessarily. However, by implementing the method disclosed, N_cip is assigned 3 which keeps the size of the model tractable and resultantly requires less computational effort to solve.
Upon computing the estimated value, the one or more hardware processors 104 define the one or more constraints corresponding to the defined flow shop scheduling information. However, not all the constraints as stipulated in Table 7 are defined using the estimated value. The constraints 1 to 9 do not require the estimated value of N_cip, while the constraints 10 to 16 are defined based upon the estimated value of N_cip. The objective function is weight×makespan+cip_dist, wherein the weight parameter is defined in Table 1 and the makespan and cip_dist are identified as the variables. When the optimizer finds the optimal solution subject to the constraints mentioned previously, cip_dist is minimized thus setting the value of the variable cip_j^start to the minimum of startT_(i,j) for all machines.
The one or more hardware processors 104 are then configured to optimize the flow shop scheduling of the manufacturing plant using the one or more constraints. The one or more hardware processors 104 communicate the one or more constraints and the flow shop scheduling information to an Optimizer Module (not shown in the figure) to obtain an optimum flow shop schedule. By referring to Table 8 below, the obtained optimum flow shop schedule is shown and described.
Table 8
j 1
2 3
Cutting Welding Packing
Start time Finish time Start time Finish time Start time Finish time
i

startT_(i,j) startT_(i,j)+procT_(i,j) startT_(i,j) startT_(i,j)+procT_(i,j) startT_(i,j) startT_(i,j)+procT_(i,j)
Chair 146 176 176 196 196 211
Chest 54 79 89 114 114 144
Door 26 46 56 81 81 106
Table 81 111 116 141 146 171
Shelf 119 144 149 176 179 194
Drawer 0 25 25 55 55 80

By referring to Table 8 again, it may be noted that, the obtained optimum flow shop schedule depicts the start and completion times of each job on each machine. The schedule may be visualized in the form of a Gantt chart as shown in FIG. 4. The makespan of the optimum flow chart schedule is 211 minutes. The last job (chair) of the flow shop scheduling is finished on packing machine after 211 minutes. The value of the objective obtained is 212328. The jobs are processed in the order drawer, door, chest, table, shelf, and chair. Thus, optimum flow shop schedule comprises optimal order in which the jobs must be processed is obtained.
Table 9
j 1
2 3
Cutting Welding Packing
cipT_(j,n) Start time Finish time Start time Finish time Start time Finish time
First CIP process (n=1) 46 54 81 89 106 114
Second CIP process (n=2) 111 119 141 149 171 179
Third CIP process (n=3) 179 187 209 217 239 247

By referring to Table 9 above, the start and end times of the CIP process (arising due to the time dependent changeover) for each machine may be referred. As evident from the values in Table 9 above again, the step of processing no product or job during CIP process has been successfully implemented. No job is processed on cutting machine from time 46 minutes to 54 minutes, from 111 minutes to 119 minutes and from 179 minutes to 187 minutes which are CIP process phases for cutting machine. Similar observations may be made for rest of the two machines.
Further, may be observed from FIG. 4, at least one job is processed between two CIP processes on all the machines. Also, first CIP process is executed before second and second before third as may be observed from Table 9 above. The difference between two CIP process times is less than or equal to (interval^cip+duration^(cip )= 60+8) 68 minutes (64 between first and second CIP process on Cutting machine and 66 minutes between first and second CIP process for Packing machine). Thus, the CIP processing times are set free and not constrained to be only after every 68 minutes. Also, no time window needs to be provided for the CIP processing times. This facilitates overall better performance in the process of flow shop scheduling.
By referring to Table 10 below, it may be noted that the value of cip_dist is obtained 1328. The values of variables cip_j^start and k_(j,n) may be referred to in Table 10. The values of cip_i^start are set to the start of the first job (drawer) on each machine which can be verified from Table 8 supra. The values of all k_(j,n) are 1. This implies that the constraint of processing at least one job between CIP process phases is always active. Some jobs are still to be processed between first and second CIP process, as well as between second and third CIP process, and all the jobs are finished processing only after third CIP process for all the machines.
Table 10
j 1 2 3
Cutting Welding Packing
cip_j^start 0 25 55
n=1 n=2 n=1 n=2 n=1 n=2
k_(j,n) 1 1 1 1 1 1

Table 11
j 1
2 3
Cutting Welding Packing
n=1 n=2 n=3 n=1 n=2 n=3
Chair 1 1 0 1 1 0
Chest 1 0 0 1 0 0
Door 0 0 0 0 0 0
Table 1 0 0 1 0 0
Shelf 1 1 0 1 1 0
Drawer 0 0 0 0 0 0

Finally, by referring to Table 11 above, the values of variable afterCIP_(i,j,n) obtained after optimization may be referred. Considering an example a scenario, wherein, i=Drawer, for machine cutting. For all n, the value of variable after afterCIP_(i,j,n) is 0, which implies that the drawer was processed before the first, second and third CIP process which can be confirmed from the FIG. 4. To explain further, consider the case of chair. By referring to Table 9 yet again, it may be observed as for all the three machines, chair was processed after first CIP process and the second CIP process, but before third CIP process. These interpretations can be validated by referring to FIG. 4 and Table 8 yet again.
The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments. The scope of the subject matter embodiments is defined by the claims and may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope of the claims if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language of the claims.
It is to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g. any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g. hardware means like e.g. an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g. an ASIC and an FPGA, or at least one microprocessor and at least one memory with software modules located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments may be implemented on different hardware devices, e.g. using a plurality of CPUs.
The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various modules described herein may be implemented in other modules or combinations of other modules. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.
The illustrated steps are set out to explain the exemplary embodiments shown, and it should be anticipated that ongoing technological development will change the manner in which particular functions are performed. These examples are presented herein for purposes of illustration, and not limitation. Further, the boundaries of the functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternative boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. Such alternatives fall within the scope and spirit of the disclosed embodiments. Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein and in the appended claims, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise.
Furthermore, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store instructions for execution by one or more processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer-readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., be non-transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, nonvolatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media.
It is intended that the disclosure and examples be considered as exemplary only, with a true scope and spirit of disclosed embodiments being indicated by the following claims.