FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
Title of invention:
A METHOD AND SYSTEM FOR RAPID, OPTIMAL AND FEASIBLE SCHEDULING OF PROCESSES ON A SET OF PARALLEL AND DISSIMILAR PROCESSORS
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.

FIELD OF THE INVENTION
The present invention relates to rapid, optima} and feasible scheduling of processes on parallel and dissimilar processors with the schedule generation methods implemented on multi-core processors. More particularly the invention relates to generation of rapid, optimal and feasible schedules on parallel and dissimilar processors using the domain-specific heuristics and domain independent meta-heuristics. These meta-heuristics are efficiently executed on a system with multiple central processing units or cores. Together they improve measures such as but not limited to system throughput and/or meet process completion deadlines.
BACKGROUND OF THE INVENTION
This invention addresses the scheduling of the various processes (such as train journeys from origin to destination on rail networks, executing a multiplicity of orders for production jobs in manufacturing plants, loading and unloading of parcel tankers with a multiplicity of commodities at multiple locations, pumping of different commodities between multiple locations over pipeline networks) on a set of parallel and dissimilar processors (such as tracks, machines, parcel tankers, pipelines, etc. respectively).
Although conventional approaches provide several mechanisms for scheduling the processes, there exist major challenges in implementing the existing approaches for scheduling processes in environments/systems wherein various, parallel and dissimilar processors are involved. Rapidity, optimality and feasibility are the major challenges for the conventional approaches for scheduling of processes on processors.
Timeliness of performing the processes is another issue which is highly desirable. Since various independent processes as well as processors are involved, the factors such as due date compliance and/or the throughput of the system of parallel and dissimilar processors become critical. While scheduling the processes on dissimilar processors there is a need to take in to consideration the cost aspects, resource requirements, process-processor compatibility constraints, corporate policies as well as legal rules to derive or obtain an implementable schedule with minimal deviations in reference to planned target level for the defined measures.
There is, thus, a long felt need to develop a method and system for the rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors, to primarily

improve measures such as but not limited to throughput and on-time performance, white optimizing costs and other factors.
However, the existing method and systems providing process scheduling are listed below. None address the lacunae stated above. Some of them known to us are as follows:
US7810094B1 to McClure et al. teaches about a executing a plurality of symmetric schedulers on respective processors of a multiprocessing system. The problem addressed particularly related to utilize scheduling information and a pre-determined round-robin scheduling algorithm to Identify a next executable one of the processes. In addition, the focus of this patent is apparently on data access (shared lock).
US7454389 to Carpenter et al. teaches about an improved scheduling and planning system in which computer implemented software uses a hierarchical selection list to select at least one of a plurality of unconnected users and contact the selected user(s) as a function of an event.
US5701482A to Harrison et al. teaches about a modular array processor architecture which comprises a plurality of interconnected parallel processing nodes. US5701482A to Harrison et al. relates to array processors, and more particularly, to modular array processor architecture with focus apparently on providing for communication between nodes & node memories. The patent addresses an adaptive task scheduling scheme for adaptive data flow balancing on processors, while groups of tasks between nodes are not balanced thus avoiding idle time on processors. It uses a predetermined set of rules that are implemented by means of a heuristic task scheduling program.
US5212791 to Damian et al. teaches about a technique that utilizes a knowledge base system to dynamically schedule production of parts on a plurality of manufacturing machines.
US4887218 to Natarajan teaches about a conceptual decision analysis tool for production release planning displays management parameters and objectives and prompts the user to define priorities.

US4852001 to Tsushima et al. teaches about a job scheduling method for scheduling of job allocation to various resources, wherein each workload of a job is allocated to each time unit along a time axis in units of job and resource type.
US4896269 to Tong teaches about a method for the efficient scheduling of a first plurality of jobs and the performance of the jobs on a second plurality of processing machines uses various heuristic rules in order to meet scheduling objectives. Initially, each job is scheduled on the machines without regard to the scheduling of any other job.
US20060015203 by Yasunobu et al. teaches about a scheduling method for preparing, after receipt of a production order schedule of finished vehicles, a production order schedule of parts necessary for the production of the finished vehicles.
US20020107600 by Myrick et al. teaches about a system and method for scheduling manufacturing resources based on user defined scheduling and routing goals. Attributes and constraints may be assigned to manufacturing resources and SKUs that facilitates the planning and scheduling of the resources.
US2002198924A1 by Hideya et al. teaches about a computer having a plurality of processors or in a computer cluster system, wherein the processing performance is improved by measuring operation characteristics of a process, and by performing process scheduling on the basis of actual measurements of the process operation characteristics. The problem addressed particularly relates to a process scheduling method that uses a priority based approach utilizing processor operation characteristics, wherein a ratio of memory access wait time to program execution time and memory access size during execution of a program. This patent addresses dissimilar processors but leverages 'memory access time' - which is specific only to computing processor environments.
WO2008148625A1 by Nechypurenko et al. teaches about a method for scheduling a predictable operation of an algorithm on a multi-core processor comprising a plurality of parallel working cores. The problem addressed particularly relates to scheduling a process or algorithm as defined might be scheduled on multiple cores and is predetermined before execution. The method uses known optimization algorithms and heuristics, like the optimization methods "Simplex" or heuristics "Simulated Annealing" or "Best-First Searches".
JP11154143A by Sunago et al. teaches about a process scheduling system for securing the optimum communication path corresponding to a dynamic communication request

from a process under execution. The problem addressed particularly relates to a system of parallel computing system which can mutually communicate. The patent teaches about assigning communicative load of the process by selecting the processor of the lowest transmission use rate for communication path generation.
Long et al. in "A heuristic real-time parallel scheduler based on task structures" addresses parallel processor scheduling by identifying task relationships and exploiting them by assuming that it is crucial in building high quality schedules for real-life applications.
Leland et al. in "Load-balancing heuristics and process behavior" addresses dynamic load balancing in a system with homogeneous processors using simple heuristics for initial placement and processor migration of the existing processes to processors with fewer resident processes.
Eles et al. in "Process scheduling for performance estimation and synthesis of hardware/software systems" teaches about an approach based on list scheduling heuristics and branch and bound strategies. Their experiments also compare the superiority of the proposed approach over critical path heuristics and ILP based methods. The paper applies the approach to process scheduling for embedded systems.
Sih et al. in "A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures" teaches about an approach based on list scheduling heuristic viz., Highest Levels First with Estimated Times (HLFET) algorithm, an extension of Hu's classic work published in 1961 in Operations research Journal.
Ibarra et al. in "Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors" addresses the problem of finding a schedule whose finishing time is as smaU as possible. The paper looks at five different types of approaches using only processing time data to compute the finish times of the jobs.
Ghedjati in "Heuristics and a hybrid meta-heuristic for a generalized job-shop scheduling problem" address minimizing job completion time problem with unrelated parallel machines and with precedence constraints between jobs operations. They explore only heuristics that depend on potential load on the machines as well as hybrid genetic algorithm meta-heuristic.

The above mentioned prior arts fail to disclose an efficient method and system for rapid, optimal and feasible scheduling of processes which can utilize a set of parallel and dissimilar processors.
Thus, in the light of the above mentioned background art, it is evident that, there is a need for such a solution that can provide rapid, optimal and feasible scheduling of processes on a set of parallel and dissimilar processors for optimizing and increasing the efficacy of processes planning and scheduling. There is also a need for such a solution that can provide the schedule generation methods implemented on multi-core processors.
OBJECTIVES OF THE INVENTION
In accordance with the present invention, the primary objective is to provide a method and system for rapid, optimal and feasible scheduling of processes.
Another objective of the present invention is to provide a method and system for rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors with the schedule generation methods implemented on multi-core processors, wherein various independent processes are involved.
Another objective of the invention is to provide a method and system for rapid, optimal and feasible scheduling of large multiplicities of processes on large multiplicities of parallel and dissimilar processors by using the domain specific heuristics.
Another objective of the i nvention is to ensure rapid, optimal and feasible schedule generation by controlling the use of the domain-specific heuristics with domain-independent meta-heuristics and executing the said meta-heun'stics in parallel on multiple CPUs/Cores.
Another objective of the invention is to ensure rapid, optimat and feasible schedule generation by controlling the use of the domain-specific heuristics with domain-independent meta-heuristics. In the meta-heuristics a conflict resolution mechanism is introduced to select one of the best process-processor pair. Conflicts, if any, in selection and allocation of processes due to uncertainty in the choice of heuristics or due to noise in the data due to systemic errors are resolved using a tolerance-interval based approach.

Another objective of the invention is to ensure rapid, optimal and feasible schedule generation by controlling the use of the domain-specific heuristics with domain-independent meta-heuristics wherein multipl e heuristics are used simultaneously and then ranked at a common scale while deciding the selection of process-processor pairs for allocation.
Another objective of the invention is to ensure rapid, optimal and feasible schedule generation by generating multiplicity of feasible schedules using domain-specific heuristics & domain-independent meta-heuristics and then giving choice to user to select the best schedule from the multiplicity of schedules generated.
Another objective of the invention is to ensure rapid, optimal and feasible schedule generation wherein the some processes may be pre-scheduled on some processors and/or some processors may be unavailable for some known time periods within the plan horizon.
Yet another objective of the invention is to provide a method and system for the rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors with the schedule generation methods implemented on multi-core processors, allowing users to state cost and other factors to guide the choice of the best or optimal schedule among the feasible ones. Users may also specify the 'set-up time' to begin the execution of a process on a processor and such set-up time may depend on the process-processor pair as well as the process sequence on the processor. Users may also specify the dependency of the processes-processor on the dynamic availability of material and human resources.
Still another objective of the invention is to provide a method and system for the rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors, by allowing users to control, preplan and edit the schedules to meet the real operating situations.
The present invention of obtaining schedules for processes on a set of parallel and dissimilar processors using do ma in-specific heuristics as well domain-independent meta-heuristics is not limited to specific environments and is also applicable to all environments where there exists a plurality of processors and the processes are executed on these processors in multiple steps with a pre-defined routing pattern. This involves scheduling first the processes on those processor groups that are throughput or performance

bottlenecks using the said methods and then subsequently scheduling the processors in the upstream and the downstream to meet the commitments on the bottleneck.
SUMMARY OF THE INVENTION
Before the present methods, systems, and hardware enablement are described, it is to be understood that this invention in not limited to the particular systems, and methodologies described, as there can be multiple possible embodiments of the present invention which are not expressly illustrated in the present disclosure. It is also to be understood that the terminology used in the description is for the purpose of describing the particular versions or embodiments only, and is not intended to limit the scope of the present invention which will be limited only by the appended claims.
The present invention provides a method and system for rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors with the schedule generation methods implemented on multi-core processors.
In one embodiment of the invention a method and system is provided for rapid, optimal and feasible scheduling on parallel and dissimilar processors with the schedule generation methods implemented on multi-core processors, wherein various processes are to be executed independently i.e. the execution of one process does not need any of the other processes and no more than one process can be executed on more than one processers simultaneously.
In an embodiment of the invention a method and system is provided for rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors by using the domain-specific heuristics guided by domain-independent meta-heuristics.
In an embodiment of the invention a method and system is provided for rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors by using the domain-specific heuristics, wherein the domain-specific heuristics are controlled by domain-independent meta-heuhstics for generating the multiplicity of feasible schedules of processes on processors rapidly when implemented on multi-processor computing systems. The method comprises of the components that would generate multiple schedules and choose the best schedule or one with minimal deviations in reference to planned target level for the defined measures.

In an embodiment of the invention a method and system is provided for rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors, allowing users to state the factors for optimality and resource constraints for executing the processes as also to control, preplan and edit the schedules to meet the real operating situations.
The above said method and system are preferably a method and system for rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors with the schedule generation methods implemented on multi-core processors but also can be used for many other applications.
BRIEF DESCRIPTION OF DRAWINGS
The foregoing summary, as well as the following detailed description of preferred embodiments,, are better understood when read in conjunction with the appended drawings. For the purpose of illustrating the invention, there is shown in the drawings exemplary constructions of the invention; however, the invention is not limited to the specific methods and system disclosed. In the drawings:
Figure 1 shows a block diagram illustrating the system inputs and outputs for the system
for rapid, optimal and feasible scheduling of processes on parallel and dissimilar
processors
Figure 2 of the present invention illustrates optional system architecture for system for
rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors.
Figure 3 of the present invention illustrates the subsystems and information flows and
transforms, and the steps involved in planning and scheduling of processes on
processors.
Figure 4 of the present invention illustrates the sub-system and process/steps for
generating the plurality of schedules
Figure 5 of the present invention illustrates the sub-system and process/steps for
generating plurality of schedules on multi-core computing environment
DETAILED DESCRIPTION OF THE INVENTION
Some embodiments of this invention, illustrating all its features, will now be discussed in detail.

The words "comprising," "having," "containing," and "including," and other forms thereof, 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. Although any systems and methods similar or equivalent to those described herein can be used in the practice or testing of embodiments of the present invention, the preferred, systems and methods are now described.
The disclosed embodiments are merely exemplary of the invention, which may be embodied in various forms.
The present invention provides a method for providing rapid, optimal and feasible scheduling of processes on a plurality of parallel and dissimilar processors, the scheduling method being implemented on plurality of cores of the said processor for generating plurality of schedules, wherein the method comprises the processor implemented steps of:
a. allocating each one of the independent processes on one of the parallel and
dissimilar processors for a process-processor scheduling;
b. employing a domain-specific heuristics guided by a domain independent
meta-heuristics;
c. comparing pre-existing multiple schedules and allowing a user to select at
least one schedule from the multiplicity of schedules generated;
d. enabling the user to define and pre-configure scheduling parameters
associated with at least one planning horizon for controlling the generation of
multiplicity of schedules, wherein providing the user with options to
determine at least one scheduling parameter comprising band values,
weights, a domain-specific heuristics, and conflict resolution mechanism; for
improving measures such as system throughput to meet process completion
deadlines and
e. generating plurality of instantaneous schedules on plurality of cores
corresponding to the user selected scheduling parameters.

The present invention provides a system for providing rapid, optimal and feasible scheduling of processes on a set of parallel and dissimilar processors, the said system is comprising:
a. at least one processor having at least two cores for executing the schedule
generation methods, wherein each core of each processor are electronically
coupled therewith;
b. at least one core application server adapted to host a plurality of principal
components of the process-processor scheduling system;
c. at least one module and subsystem for user interface comprising control flow,
integration module to connect with one or more external systems;
d. at least one database, communicatively coupled with the core application
server, stored on a computer readable medium;
e. a scheduling engine adapted to run at least one process on at least one
processor;
f. at least one external systems communicatively coupled with the process-
processor scheduling system through at least one computer network;
g. a means for communication with a user interface associated with the
process-processor scheduling system;
h. a configuration module for enabling the user to pre-configure scheduling parameters comprising band value, weights, choice in using one or more domain-specific heuristics, and conflict resolution mechanism;
i. a schedule generation module for generating plurality of rapid, optimal and feasible schedules of plurality of processes by allocating the independent processes on at least one parallel and dissimilar processor using domain-specific heuristics guided by domain independent meta-heuristics and comparing multiple existing schedules and allowing users to select the optimal schedule therefrom; and
j. a modification module comprising interactive Gantt charts for manual and interactive modification or adjustment of the process-processor schedules for rescheduling of the schedule so generated for satisfaction of an operational exigencies.
The present invention provides a method and system for rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors with the schedule generation methods implemented on multi-core processors, wherein various independent processes are involved. More particularly the present invention provides a method and system for rapid, optimal and feasible scheduling of processes on parallel and dissimilar

processors using the domain-specific heuristics, wherein the domain-specific heuristics is guided by domain independent meta-heuristics for generating the multiplicity of feasible schedules rapidly when implemented on a multi-processor processors computing system,
Referring to Figure 1 is a block diagram of rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors.
The rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors comprises a processes scheduler (100). The processes scheduler (100) extracts the processes, their definitions and requirements (150C). Further, the processes scheduler (100) extracts processors and resources information from the corporate databases of processor and resources (150B). The processes scheduler (100) utilizes the domain-specific heuristics guided by domain independent meta-heuristics (150A) for generating schedules for the processes on processors (400). Further, the schedules (400) may be visualized, simulated and modified interactively (500).
Referring to Figure 2 of the present invention illustrates optional system architecture for system for rapid, optimal and feasible scheduling of processes on parallel and dissimilar processors.
In one of the preferred implementations, the system is installed at corporate location of the organization. The system would have preferably separate servers each scheduling engine, a database and core application.
The processes scheduling system (100) would have following major components
• 'Application Server' (110), which hosts the modules and subsystems for user interface (including control flow), integration module to connect with other external systems.
• 'Scheduling Engine' (120), which hosts analytical modules/components such as preprocessing and processes scheduling.
• 'Database' (140); consist of a database, which stores entire static as well as dynamic data required for system and method.
The processes scheduling system is integrated to various external systems/databases (10) such as Inventory management system, policy management system, processor management system and processes management system, etc to fetch the data such as

policy data, work progress status, processor status data, actual schedule execution, allocation details, etc through a communication network (20).
The user interface for the processes scheduling system is preferably a web based interface and it can be accessed over internet through a firewall (40) using internet browser from a desktop, a laptop or from a mobile/hand held devices like a mobile phone, a Personal Digital Assistant (PDA) (50), palm-top, mobile digital assistant, computer, laptop, notebook or personal computer. Further Viser interface for the processes scheduling system may be preferably formed based.
The scheduling engine (130) is preferably installed on a multi-core, high end central processing unit or processor server, with full RAM available to process the central processing unit intensive schedule generation.
Father the Database (140) with a large disk space is connected (a (ne data warehouse through high capacity bus and the data is downloadeq from the historical data database to the processes scheduling systems database through an ETL process (30).
Further, in another such implementation, the system may be hosted on a cloud computing environment and all the users access the application using internet, and all the modules would be installed on cloud environment.
Referring to Figure 3 of the present invention illustrates the subsystems and information flows and transforms, and the steps involved in planning and scheduling of processes on processors.
According to one of the embodiments of the present invention, Figure 3 of the present invention illustrates the subsystems and information flows, transforms, and the steps involved in planning and scheduling of independent processes on parallel and dissimilar processors; wherein the method comprises of the follovvjng steps:
150: Downloading and configuring various scheduling parameters, which are optional or mandatory, including but not limited to the policy data such as relative importance of the different scheduling goals (heuristics and meta heuristic parameters), planning interval, etc. and downloading and configuring various other scheduling parameters such as the description of the unit where processes are being managed, which includes location, hours of operations,

processes to be performed, etc and the description and constraints on the available resources; various process types, business rules applicable and optionally downloading some or all of these scheduling parameters from external system
200: Preprocessing and calculating values of various scheduling parameter and data elements required during scheduling of processes, physical parameters are calculated wherein the calculation is subjected to the combination constraints and business rules. It also includes pre-scheduling some processes on some processors or cores and/or marking the unavailability of some processors for some known time periods within the plan horizon.
300: Scheduling/allocating the processes optimally to processor wherein the allocation is subjected to the combination of objectives and constraints and business rules
400: Viewing and modifying the schedules./allocations of processes
500: Monitoring deviations in schedule and managing allocations to meet the operation exigencies due to deviation from schedule
600: Updating planned/scheduled work into data bases, (may be external)
In one embodiment of the invention, in step 150 i.e. 'Configure & Download data', various master data and scheduling parameters are configured, wherein many of these scheduling parameters/data can optionally be downloaded from relevant corporate systems or data bases. These scheduling parameters may be optional or mandatory. The above said parameters including but not limited to:
a. Policy parameters such as relative importance of the different scheduling goals,
weights for creating domain-specific hybrid heuristics and tolerance band
parameter for meta-heuristics, planning interval time granularities, etc.
b. The description of the processors information such as but not limited to the list of
processes which can be executed on the respective processor, preference for
some processes, time and cost to execute the processes, the set-up time for the
processes on that processer, availability of the processors, various resource
required to execute process etc. from relevant corporate data bases. It would also
include processors status information such as but not limited to busy, working, not
available, under breakdown, preventive maintenance etc.
c. Resources information such as but not limited to availability, linkage to process and
processors, etc.

d. Processes information such as but not limited to process start date, due information, delivery information, processing duration on various processors, routing definitions, set up requirements on processors, cost of the product, processing costs etc. It would also include work-in-progress status in processing environment information such as but not limited to inventory units at various stages of processing for processes, inventory units in front of the processors, costs of holding inventory for the holding duration, etc.
In an embodiment of the invention, processor and resources information is extracted, transformed and loaded to the scheduler from the corporate databases.
In an embodiment of the invention, in step 200 i.e. 'Preprocess Parameters', various physical quantities or parameter are calculated such as the time and cost required to perform a process on a processor (e.g. for a train to run between two stations), the setup time and cost to execute the processes, often depending on the preceding process, legal process-processor combinations, etc. It also includes pre-scheduling some processes on some processors and/or marking the unavailability of some processors for some known time periods within the plan horizon.
In an embodiment of the invention, in step 300 i.e. 'Schedule Processes', processes are allocated and scheduled to processors for creating feasible plans that optimize planning measures such as throughput, due-date performance or similar corporate goals, using a set of domain independent meta-heuristies to guide the application of a set of domain-specific heuristics.
Generation of Multiple Schedules: In an embodiment of the invention as presented in Figure 4, in step 300 i.e. 'Schedule Processes', an iterative search process is implemented to rapidly generate the multiple schedules and then an optimal schedule is selected from the generated schedules. One among the below mentioned iterative process is used to generate multiple schedules.
1) Basic iterative process: In an embodiment of the invention, in step 300 i.e. 'Schedule Processes', an iterative search process is implemented on multi-core systems to rapidly generate the multiple schedules.
1. Define the scheduling parameters

a. Define the scheduling measure: The measure against which the
schedules will be evaluated after scheduling all the processes on
processors is defined.
b. Select one or more combination of configurable domain-specific
heuristics to be used. This defines the criteria for defining the process-
processor selection from the processor queues.
c. Select the band parameter 'N' i.e. a configurable number expressed
either in absolution terms i.e. number of processes or in percentage
deviation from best value of H-value among all the processes to be
scheduled.
d. Select the weights for creating hybrid heuristics i.e. a configurable
number expressed to decide the weighted importance of a heuristic in a
hybrid heuristics.
2. Obtain feasible process-processor pairs: From the available set of processors and processes to be scheduled, the all possible combination of feasible process-processor pairs are identified in this step. The feasibility check includes but not limited to permissible process-processor combination, sequencing rules etc.
3. Calculate H-value for each process-processor pair: For each process-processor combination, a numerical value (H-value) based on the criteria is computed for the selected domain-specific heuristics (or two or more of them combined) is calculated. The numerical value computation also includes factors relevant to cost and time aspects of dependent resources required for executing the process on the processor, ex: cost and time of staff required for performing the process on the processor. The numerical value for each process-processor pair for all heuristics employed is generally computed only once unless there is any dependency of the criteria on time.
4. Sort all process-processor pairs: Then processes are sorted in ascending or descending order of the computed criteria values.
5. Randomly select a process-processor pair from the top 'N' list of process-processor pairs with best H-values (or) randomly select one from the list with an exponentially decreasing probability from the highest scoring.

6. Check the feasibility of allocation; if feasible then schedule/allocate the selected process on selected processor else chose another feasible pair from the list using method given in step 5.
7. Recalculate the H-Value - Then if required, the criteria for remaining process-processor combination is recalculated.
8. Continue till no process can be further allocated
9. Evaluate feasibility with reference to all the processes being completed within or on or before their deadlines. If feasible check is successful, go to next step else step 11.
10. Calculate the objective value of the schedule generated and store the schedule in a memory data container.
11. Loop - If multiple schedules are to be generated then go to step 1 and select either from other heuristics, or other value of band parameter or other weight for creating hybrid heuristics, repeat for all heuristics and selected combinations of band parameter and hybrid heuristics weight else go to next step
12. Select the best schedule from the multiple schedules generated in step 9. Best schedule is the one the has the combination of lowest objective function score as well as maximal or complete compliance to delivery or due-date commitments.
Ail the steps mentioned above are executed on a mufti core machine with different combinations. The above iterative process provides the following possible options for generation of multiplicity of schedules:
a) Multiple schedules are generated by simultaneously using more than one heuristics and running each one of them on different core of the processor.
b) Using more than one definition for band parameter N and running the plurality of definition on multiple cores.
2) Alternate iterative process: In another embodiment of the invention, in step 300 i.e. 'Schedule Processes', an alternate iterative search process as an alternate is also implemented to rapidly generate the multiple schedules. The step 5 in the Basic Iterative Process is replaced with the following process-processor selection mechanism:

5. Select a process-processor pair by comparing H-value of each one of the process-processor pairs with other process-processor pairs:
a. If H-value of the incumbent is significantly better i.e. better by 'm' %
(tolerance interval) compared to the other pairs, select the incumbent pair
for allocation.
b. If H-value of the incumbent is significantly worst i.e. worst by 'm' %
(tolerance interval) compared to the incumbent values, reject the
process-processor pair and choose next in the list for evaluation.
c. If current H-value and incumbent is within range of +- 'm' % (tolerance
interval) compared to the incumbent value, randomly decide whether to
select or reject the pair
The alternate iterative process introduces a conflict resolution mechanism through which, conflicts, if any, in selection and allocation of processes while evaluating the criteria due to ambiguity in the heuristics definitions (or) due to noise in the data due to systemic errors are resolved using a tolerance interval based approach with randomization while evaluating the process-processor pairs.
Multi Core Processing: In an embodiment of the invention, in step 300 i.e. 'Schedule Processes', multi-core computational system is used to implement the coarse-grained parallelizable meta-heuristics for scheduling a set of processes to a set of parallel and dissimilar processors in environments or industries like manufacturing such as job shops, services such as trains, parcel tankers, pipelines, contact centers etc. such that the processes are completed by their due-dates or to maximize the throughput of the system of processors {for example a set of machines, a pipeline network). The schedules are feasible with respect to the pairing of processes and processors, the sequence of processes or the use of limited other resources by the processes. The computation of the schedules is very rapid.
In one of the embodiment of the invention as presented in Figure 5, multiple schedules would be generated using multiple cores of the scheduling engine by generating plurality of schedules on each core of machine using a threading mechanism that will effectively use all the cores of the scheduling engine effectively, The system would either be using same domain-specific heuristics and domain independent heuristics to plurality of

schedules on each core of the scheduling engine thus generating multiple schedules within shortest time and then choosing the best schedule from the generated ones.
Adjustable band and weights: In an embodiment of the invention, in step 300 i.e. 'Schedule Processes', the process includes a mechanism to set the value of the control parameters (i.e., band parameter and weights on heuristics) and a pre-configured rate of change on these parameters to enable generation of multiplicity of schedules as well as convergence or exit of the process automatically as the search for optimal solution proceeds. The initial values of the control parameters and the rate of change are adjustable parameters.
Heuristic explained and Sequence dependent setup time: In an embodiment of the invention, in step 300 i.e. 'Schedule Processes', configurable domain-specific heuristics i.e. criteria for selection from process queues, includes but not limited to deadline, processing times, weighted sum of deadlines and processing times etc., wherein the processing time includes set up times, which in turn may be dependent on what process is being processed on an processor prior to allocation of process under consideration.
Feasibility Check: When a process-processor pair is selected for evaluation, the feasibility of allocation, in terms of whether the processor can process the process, which additional resources are required as well as availability of the resources, valid sequence of the process allocation, etc., are considered. Violating the feasibility rules mentioned above leads to infeasible schedule. Using configuration module, user can select the constraints and rules to be used for checking the feasibility of an allocation as well as state whether the constraints/rules are mandatory or desirable to meet or satisfy. Feasibility check on each one of the generated schedule is carried out to ensure that all the processes are scheduled on the processors are completed on or before their deadlines (due-dates).
On-line Scheduling: In an embodiment of the invention, in step 300 i.e. 'Schedule Processes', the scheduling of processes happens at real time or run time i.e. processes are scheduled on processors as and when they enter into the system. As the scheduling problem is nondeterministic polynomial time (NP) complete problem, it requires huge processing and the schedule generation is central processing unit bound, thus require high end central processing unit and random access memory available.
Theory of Constraints approach: The present invention of obtaining schedules for processes on a set of parallel and dissimilar processors using domain-specific heuristics

as well domain-independent meta-heuristics is not limited to specific environments and is applicable to all environments where there exists a plurality of processors and a plurality of processors and the processes are executed on these processors in multiple steps with a pre-defined routing pattern, by beginning with the scheduling of those process-processor groups that are throughput or performance bottlenecks. The upstream and downstream as well as other parallel critical processors or resources are scheduled after finalizing allocation on bottleneck processor/s so as to feeds or consumptions to the bottlenecks are not affected.
Further in step 400 i.e. 'View and Modify Schedules', the system provides a module for accommodating and facilitating adjustments or editing of the generated schedule by the planners or users via an interactive Gantt-Chart train and a simulation engine to improve appiicability of the generated schedule. Further system provides a module for simulating various scenarios and performs what-if analysis. The view depicts the impact (e, g, cost or violation of constraints, business rule etc) of any changes made to the schedule so as to guide the user. Changes in the schedule can be retracted and saved when finality is achieved.
Further in step 500 i.e. 'Monitor and manage deviations', the system for scheduling of processes provides a module to facilitate the monitoring of deviations from the planned schedule during day-to-day operation via an agile real time alert generation mechanism and managing allocation, and enabling the re-computation, modification or adjustment of the process allocations to meet the day of operations exigencies based on the output of the earlier steps.
Further, in step 600 i.e. 'Update Data', the system for scheduling of processes provides a module to facilitate updating planned/scheduled work into various systems, may be external one.
The preceding description has been presented with reference to various embodiments of the invention. Persons skilled in the art and technology to which this invention pertains will appreciate that alterations and changes in the described structures and methods of operation can be practiced without meaningfully departing from the principle, spirit and scope of this invention.

ADVANTAGES OF THE INVENTION:
• The invention provides a system and method for rapid, optimal and feasible scheduling of processes on a set of parallel and dissimilar processors, and is applicable in various domains such as but not limited to scheduling of production orders in manufacturing plants, pipeline scheduling, tanker scheduling, order allocation in services industry as well as scheduling of trains on rails.
• The invention provides the user with the option of generation of multiplicity of schedules in shortest possible time by using the power and configuration of modern hardware such as multiple cores by generating plurality of schedules on each core of the multi-core scheduling engine;
• The invention provides the user with the option of generation of multiplicity of schedules for evaluation by enabling the user to pre-configure parameters that control the schedule generation i.e., band value, weights, choice in using one or more heuristics, conflict resolution mechanism, etc.
• Provides for hardware and network support in a plurality of efficient architecture and configuration options
• Provides a scalable and time efficient system and method for the development of processes schedules that optimize throughput, due-date performance or similar corporate goals and thus provide the schedules that are practically usable as well as easy to implement while meeting user-defined sets of statutory, corporate or union rules or constraints, thereby ensuring that the schedules are legally and otherwise fit for implementation.
• Provides a system and a method for the easy and effective interactive mechanism using Gantt Charts and Simulators for modification and changes to the schedules to improve their applicability on continual basis.
• The proposed system is applicable to all environments where there exists a plurality of processors and the processes are executed on these processors in multiple steps with a pre-defined routing pattern. This involves scheduling first the processes on those processor groups that are throughput or performance bottlenecks using the said methods and then subsequently scheduling the processors in the upstream and the downstream to meet the commitments on the bottleneck.

WE CLAIM:
1. A method for providing rapid, optimal and feasible scheduling of processes on a
plurality of parallel and dissimilar processors, the scheduling method being
implemented on plurality of cores of the said processor for generating plurality of
schedules, wherein the method comprises the processor implemented steps of:
a. allocating each one of the independent processes on one of the parallel and
dissimilar processors with the objective of improving at least one of measures
such as system throughput to meet process completion deadlines;
b. employing a domain-specific heuristics guided by a domain independent
meta-heu ristics;
c. comparing pre-existing multiple schedules and allowing a user to select at
least one schedule from the multiplicity of schedules generated;
d. enabling the user to define and pre-configure scheduling parameters
associated with at least one planning horizon for controlling the generation of
multiplicity of schedules, wherein providing the user with options to
determine at least one scheduling parameter comprising band values,
weights, a domain-specific heuristics, and conflict resolution mechanism; and
e. generating plurality of instantaneous schedules on plurality of cores
corresponding to the user selected scheduling parameters.
2. The method as claimed in claim 1, further comprising the processor implemented
steps of:
a. facilitating the users to choose and define at least one of the planning
measures comprising maximizing throughput profit, deadline compliances,
maximizing processing volumes, maximizing revenues for the pre-defined
time period according to the planning horizon;
b. facilitating the generation of process-processor schedules in real time mode
using domain dependent heuristics guided by domain independent heuristics
for selection of the processes in processor queues to load the processes on
the processors; and
c. facilitating simulation of the processing environment using the set of domain
dependent and independent heuristics to determine optimal combinations of
alternatives for the chosen planning measures in the pre-defined time period
within the planning horizon.

3. The method as claimed in claim 1, further comprising the processor implemented
steps of:
a. downloading data related to business policy, processors & their current status
and resources data from at least one external systems integrated to the
process-processor scheduling system through at least one computer
network;
b. extracting, transforming and loading the processes related data comprising
current and new processes to be scheduled on a database of the process-
processor scheduling system from the data ware house system using a
Extract, Transform and Load processor (ETL processor);
c. preprocessing various parameters based on user defined parameters for
scheduling, wherein the parameters include sub-module for determining
process-processor scores using various domain dependent heuristics and
sub-module for selection of process-processor pair and loading the process
on the processor;
d. pre-scheduling processes on processors for marking the unavailability of
some processors for some known time periods within the planning horizon;
e. viewing and optionally modifying the generated processes schedule including
steps for system simulation; and
f. transferring the planned and scheduled allocations into external data bases.
4. The method as claimed in claim 1, wherein the process-processor scheduling is
integrated with plurality of operations handling systems comprising of an order
management system, a policy management system and a resource management
-J system for fetching and downloading of data associated with processors, processes,
polices & resource through a computer network.
5. The method as claimed in claim 1, wherein each scheduling parameters having static
or dynamic characteristics comprises of relative importance of the different
scheduling heuristics, planning interval time granularities, scheduling engine
parameters, description of the unit, description and constraints of the available
processors and resources, various processes, and processes types or applicable
work rules.

6. The method as claimed in claim 1, the user is accessing each of the process-processor schedules and planning horizon thereof, wherein the user is provided with an interactive Gantt charts to manually modify or reschedule at least one process of at least one day in accordance with the operations exigencies thereof.
7. The method as claimed in claim 1, wherein the multiple schedules are generated using multiple cores of the scheduling engine by generating plurality of instantaneous schedules on each core of machine using plurality of concurrently running threads on plurality of the cores of the scheduling engine, wherein employing same domain-specific heuristics or different heuristics to generate multiple schedules for obtaining an optimal schedule with in shortest time.
8. A method for scheduling of processes on a plurality of parallel and dissimilar processor for allocation of independent process to parallel processors comprises the processor implemented steps of:
a. defining the scheduling measure, selecting at least one combination of
configurable domain-specific heuristics to be used and selecting the band
parameter 'N' and the weights for creating hybrid heuristics;
b. obtaining feasible process-processor pairs;
c. calculating H-value for each process-processor pair;
d. sorting all process-processor pairs;
e. selecting process-processor pair according to at least one selection criterion
thereof, wherein the selection criterion comprises selecting process-
processor pair randomly from the top *N' list of process-processor pairs with
best H-values, randomly selecting at least one from the list with an
exponentially decreasing probability from the highest scoring, and selecting a
process-processor pair by comparing H-value of each one of the process-
processor pairs with other process-processor pairs and randomly choosing
the pair that falls within the set tolerance levels.
f. checking the feasibility of allocation;
g. recalculating the H-Value for satisfaction of predetermined requirement;
h. continuing processes till no process is available for further allocation;
i. evaluating feasibility with a reference process to all the processes being
completed within or on or before their deadlines; j. calculating an objective value of the schedule generated for true of the
feasibility check and storing the schedule in a memory data container;

k. changing parameters for regenerating schedule for false of the feasibility
check; and I. selecting the thus optimized schedule from the multiple schedules generated.
9. The method as claimed in claim 8, wherein the process-processor scheduling further comprises the processor implemented steps of: capturing all the variables defined in relation to process information comprising order date, due/delivery information, processing duration on various processors, routing definitions, set up requirements on processors, cost of the product, processing costs, and work in process status associated with a processing environment information.
10. The method as claimed in claim 8, wherein the captured variables facilitating a decision support and responding to the user via a query system to access the variables captured in the database.
11. The method as claimed in claim 8, further comprises of methods of displaying the list of process-processor pairs in front of each of the processors in the processing environment as per the existing and newly tested scheduling alternatives.
12. The method as claimed in claim 8, further comprises of displaying values for the management objectives defined by the user as per the current definitions as well as correlated with said newly tested alternatives.
13. A system for providing rapid, optimal and feasible scheduling of processes on a set of parallel and dissimilar processors, the said system is comprising:
a. at least one processor having at least two cores for processing, wherein each
core of each processor are electronically coupled therewith;
b. at least one core application server adapted to host a plurality of principal
components of the process-processor scheduling system;
c. at least one module and subsystem for user interface comprising control flow,
integration module to connect with one or more external systems;
d. at least one database, communicatively coupled with the core application
server, stored on a computer readable medium;
e. a scheduling engine adapted to run at least one process on at least one
processor;
f. at least one external systems communicatively coupled with the process-
processor scheduling system through at least one computer network;

g. a means for communication with a user interface associated with the process-processor scheduling system;
h. a configuration module for enabling the user to pre-configure scheduling parameters comprising band value, weights, choice in using one or more domain-specific heuristics, and conflict resolution mechanism;
i. a schedule generation module for generating plurality of rapid, optimal and feasible schedules of plurality of processes by allocating the independent processes on at least one parallel and dissimilar processor using domain-specific heuristics guided by domain independent meta-heuristics and comparing multiple existing schedules and allowing users to select the optimal schedule therefrom; and
j. a modification module comprising interactive Gantt charts for manual and interactive modification or adjustment of the process-processor schedules for rescheduling of the schedule so generated for satisfaction of an operational exigencies.
14. The system as claimed in claim 13, further comprises a scheduling engine, wherein the scheduling engine consists of an analytical module comprising preprocessing and scheduling module.
15. The system as claimed in claim 13, wherein one or more databases are connected to data warehouse of external system for downloading data therefrom for processes scheduling using a Extract, Transform and Load (ETL) processor.
16. The system as claimed in claim 13, wherein the process-processor scheduling system is accessible through a web based user interface connected over a communication network.
17. The system as claimed in claim 13, wherein the communication means is select from a group comprising of a mobile phone, a Personal Digital Assistant (PDA), palm-top, mobile digital assistant, computer, laptop, notebook or personal computer.