MXPA97002050A

MXPA97002050A - Filter system of priority row and metodode operac

Info

Publication number: MXPA97002050A
Application number: MXPA/A/1997/002050A
Authority: MX
Inventors: C Hogge John
Original assignee: I2 Technologies Inc
Priority date: 1994-09-28
Filing date: 1997-03-18
Publication date: 1997-06-01

Abstract

The present invention relates to a priority row filtering system. A filtered priority row comprises a remaining game and a filtered game. The filtered game contains a first subset of data records. The first subset of data records forms sub-levels of a network. The remaining game contains a second subset of data records. The second sub-game of data recording comprises the network heads of the network. A draw module is attached to the filtering module. The draw module is operable to access the remaining game and is also operable to order the data records in the second subset of data records to identify a data record of a more critical entity.

Description

PRIORITY FILTER FILTERING SYSTEM AND METHOD OF OPERATION TECHNICAL FIELD OF THE INVENTION This invention relates in general to the field of electronic systems, and more particularly to a system for filtering the priority row of computer programs and to a method of operation.

FIELD OF THE INVENTION Conventional computer systems often use a priority row of entities drawn by some set of comparison criteria. Entities can represent tasks that a computer system can perform or data that a computer system must process. The priority row is used to order those tasks. The entity at the top of the priority row is the most critical entity. This entity represents the task that the computer program system must perform immediately. A computer program system using the priority row removes the most critical entity from the priority row and performs the tasks appropriate to that entity. The computer program system then searches for the priority row listing the remaining entities in order of importance. The most critical entity again occupies the top point of the priority row.

A variety of draw mechanisms are used in conventional computer program systems to bypass entities in the priority row. Two of these draw mechanisms are mentioned as a quick draw and a raffle. These conventional draws classify all entities in the priority row in order from the most critical to the least critical. The lottery criterion generally depends on fixed characteristics of the entities defined as appropriate for the tasks represented by the entities. The fixed characteristics can be such things as a product number, a due date, an amount, manufacturing costs, and profit margin with respect to a priority row of entities representing orders for items produced by a manufacturing plant. The raffle criteria may include non-fixed preferences that change during the time in which the computer program system processes the priority row and performs the tasks. For example, a computer program system may prefer entities of a second type for a certain period of time after processing an entity of a first type.

The draw of the priority row after each critical entity is removed is costly and time consuming. This is especially true with respect to priority rows that use non-fixed preferences in the draw criteria.

An alternate method for ordering entities is a network structure rather than a drawn row. Some systems of computer programs build a network by placing some entities in order with respect to each other but not bypassing all entities. These computer program systems can perform a network vertex removal that determines the network heads after the removal of a network entity. However, the network of these systems does not provide an indication of the most critical entity.

SYNTHESIS OF THE INVENTION Therefore, a need has arisen for a computer program system using an improved priority network and an operating method that reduces the time and expense required to bypass the entities in the priority row.

In accordance with the present invention, a network system is provided that utilizes a filtered priority network and a method of operation that virtually eliminate or reduce the disadvantages and problems associated with conventional priority rows and methods for bypassing priority rows .

According to one embodiment of the present invention, a computer program system utilizing a filtered priority network is provided. A The filtering module is operable to access a plurality of data records of entities of a priority row and to filter and arrange the data records in a memory storage device to form the filtered priority row. The filtered priority row comprises a remaining game and a filtered game. The filtered game contains a first subset of data records. The first subset of data records form sublevels of a network. The remaining game contains a second subset of the data records. The second subset of data records comprises network heads of the network. A draw module is coupled to the filtering module. The draw module is operable to access the remaining game and to order the data records in the second subset of data records to identify a data record of a more critical entity.

BRIEF DESCRIPTION OF THE DRAWINGS A more complete understanding of the present invention and the advantages thereof can be gained with reference to the following description taken in conjunction with the accompanying drawings in which the like reference numerals indicate like characteristics and wherein: Figure 1 illustrates a computer program system using a filtered priority row constructed in accordance with the teachings of the present invention; Y Figure 2 illustrates a flow scheme of a filtering and racking method of a priority row according to the teachings of the present invention.

DETAILED DESCRIPTION OF THE INVENTION The teachings of the present invention are applicable to computer program systems using priority rows to order entities representing tasks that need to be carried out. Entities comprise data records stored and arranged in a memory storage device. Computer program systems operate on computer apparatus systems capable of accessing data records, moving data records into a processing memory and carrying out processing steps on data records as described herein. The present invention reduces the time and cost to order entities to identify a more critical entity.

Figure 1 illustrates a computer program system 2 using a filtered priority row constructed in accordance with the teachings of the present invention. The computer program system 2 includes a filtering module 4 coupled to a draw module 6. The filtering module 4 and the draw module 6 are coupled to a memory storage device 8. The memory storage device 8 it supports a filtered priority row 10. The filtering module 4 accesses all the entities in the filtered priority row 10, and the draw module accesses only those entities maintained in a remaining game 12.

The filtered priority row 10 comprises the set of remaining entities 12 and the filtering set of entities 14. The entities comprise the data registers stored in a memory storage device 8. The entities in a filtered priority row 10 are arranged in a memory storage device 8 in a network as shown. The remaining game 12 includes the network heads. The filtered game 14 includes all entities that are not network heads.

Remaining set 12 includes entity 16 and entity 18. Entity 16 and entity 18 are network heads. The filtered game 14 includes 3 sub-levels of the network. Entity 20 and entity 22 occupy a first sub-level, entity 24 and entity 26 occupy a second sub-level, and entity 28 occupies a third sub-level. The entities in a filtered priority row 10 are interrelated as shown by the network structure.

The filtered priority row 10 includes the entities representing the tasks that the computer program system 2 must perform. The computer program system 2 uses a filtered priority row 10 to determine which of the entities is the most critical and must be removed immediately from the filtered priority row 10. The most critical entity is that entity in the filtered priority row 10 which is the most important according to the defined lottery criteria.

The filtering module 4 operates to generate the network structure of the filtered priority row 10. The filtering module 4 filters and arranges the data records of the entities in the memory storage device 8 according to the draw criteria defined. After the filtering module 4 filters and arranges the data records, the filtered game 14 comprises a subset of filtered priority row 10 containing all the entities that do not need to be drawn because they can not comprise the most critical entity. The remaining game 12 comprises a subset of the entities in the filtered priority row 10 that could comprise the most critical entity.

The draw module 6 operates to order the entities in the remaining game 12 according to a draw based on the defined draw criteria. The draw module 6 also uses additional criteria to resolve any ambiguities or berths. As shown, entity 16 is the most critical entity, and entity 18 is next most critical after entity 16. Entities in filtered game 14 are ordered from one sub-level to the next, but are not ordered with respect to all entities in the same sub-level.

A technical advantage of the present invention is that the computer program system 2 determines the most critical entity by circumventing the entities in the remaining game 12 rather than bypassing all the entities in the filtered priority row 10. This draw operation determines more quickly the most critical entity because the remaining game 12 always comprises the same or a smaller number of entities than the full filtered priority row 10.

The defined draw criteria is used to determine the network structure of the filtered priority row 10 and to determine which entities are members of the remaining game 12. The defined draw criteria comprises a number of fixed, quantified preferences for each entity included as data in the registry of relevant data. For example, if the system of the present invention were used in a manufacturing order application, a fixed preference may comprise the manufacturing cost or the profit margin of a particular product manufactured in a manufacturing factory. The raffle criteria may also include variable or dynamic preferences that change with respect to time.

The filtering module 4 determines the relationship between the entities and the remaining game 12 and the filtered game 14 based on the fact that, for any two entities, the second is known as not being the most critical entity if the first has higher values for all fixed preferences. In other words, if the amounts of fixed preferences associated with the first entity are greater than those associated with the second entity for all fixed preferences in the defined lottery criterion, the second entity can not be the most critical entity. This is true because the first entity will necessarily be located at the front of the second entity if all the entities in the priority row were drawn.

In one embodiment of the present invention, the filtered priority row 10 includes entities representing orders for products manufactured by a factory. In this embodiment, an order having a higher profit margin and a lower manufacturing cost is preferred. Therefore, the most critical entity is that entity that represents an order having the lowest manufacturing cost and the highest profit margin. According to the teachings of the present invention, the entities are filtered and drawn according to these fixed preferences.

If these fixed preferences were used to generate a filtered priority row 10, entity 16 would represent an order having a lower manufacturing cost and a higher profit margin than both entity 20 and entity 22.

Similarly, entity 18 has a lower manufacturing cost and a higher profit margin than entity 22. Entity 10 is more preferred in both preferences than entity 24 and entity 26, and entity 22 Finally, entity 26 is more preferred than entity 28. Only entity 16 or entity 18 can comprise the most critical entity because only these two entities are not less preferred than one with respect to another entity. In this modality, the most critical entity was determined by drawing entity 16 and entity 18 rather than bypassing all seven entities.

The present invention provides a benefit for any priority row application in which fixed preferences are more important than variable preferences in determining the most critical entity. This invention has been advantageous involving variable preferences that do not change frequently during processing of the priority row. In such a case, stable variable preferences can be treated as fixed preferences. When entities in the variable preferences prefer to associate with a feature change, the network structure of the filtered priority row must be rebuilt.

Figure 2 illustrates a flow scheme of a method for filtering and sorting a priority row according to the teachings of the present invention. The method is carried out by a computer program operating to order entities comprising data records in a memory storage device.

The fixed preferences that represent the defined draw criteria are selected in step 30. The fixed preferences can comprise any quantifiable parameter associated with each of the entities in the priority row. The fixed preferences are included in the data records of each entity. In a manufacturing programming environment, these fixed preferences can include the data associated with an order for the products. In step 32, the computer program system quantifies the fixed preferences for each entity in the priority row. A network structure that sorts the entities in the memory storage device is then constructed by forming a priority row filtered in step 34 based on the quantized fixed preferences of all entities. In one embodiment of the present invention, the network is structured such that an entity that is preferred over a second entity according to each of the fixed preference is placed ahead of the second entity in the network. Figure 1, described above, illustrates a filtered priority row having such a network structure. Each entity in a sub-level of the network has at least one fixed preference which is preferred over another entity in that sub-level. Therefore, the entities that occupy the same sub-level of the network are not ordered one with respect to another.

After the filtered priority row network was constructed, the computer program system identifies a remaining set of network heads, in step 36. The computer program system may repeat through the network entities, or the network data structure in the storage device can provide access to the network heads such as in a linked list. The network heads are those entities not following another entity in the network. The remaining set of network heads is drawn in step 38 according to the fixed preferences. Any ambiguities or moorings are resolved using additional criteria. In step 40, the first entity determined by the draw is removed from the priority row and processed. This first entity comprises the most critical entity. The priority row is then verified in step 42 with respect to additional entities. If there are additional entities, the computer program system continues to step 36. If there are no more entities in the priority row, then the priority system has completed processing of the entities.

The priority row is filtered and sorted in this way. The network structure of the filtered priority row is constructed by filtering the entities according to the fixed preferences associated with the entities. As shown in Figure 1, the network comprises a directed graph of vertices and edges without cycles. Each vertex has zero or more edges coming to it and zero or more edges coming out of it. Entities comprise the vertices of the network. The Network edges are determined by a function of fixed preferences quantified with respect to each entity as described above. A first entity precedes a second entity in the network only if the first entity is preferred in all fixed preferences over the second entity. Not every pair of entities in the priority network must be compared in the filtering of the priority row to form the network. The worst-case operation for N entities is that ((N2-í-2) + N) must be compared. The typical case operation is much better. In the best possible case, only N comparisons should be made.

As shown in Figure 1, the filtered game 14 of the filtered priority row 10 comprises those entities that are preceded by other entities in the network. The remaining game 12 comprises those entities that are network heads and do not have preceding entities. Only the entities in the remaining 12 entity game need to be drawn to determine the most critical entity according to the teachings of the present invention. The filtered game 14 is updated efficiently by a loop through the edges going from a more critical entity removed to other entities after the most critical entity is removed. Any entities that were preceded only by the removed entity become members of the remaining game 12 because they become the network heads.

A technical advantage of the present invention is a reduction in the number of entities to be drawn in the priority row to determine a more critical entity due to filtering of the priority network. The present invention provides a decrease in the amount of time required to bypass the priority row due to this identification of a subset of entities known as not being the most critical entity. This filtered game is removed from the draw, and only the remaining entities are drawn to determine the most critical entity.

Another technical advantage of the present invention is the fact that when the most critical entity is removed from the priority row, the remaining game of the network heads is efficiently re-computed and re-drawn without having to draw all the entities . A further technical advantage of the present invention is that the filtering of the priority row to determine a remaining set of network heads makes efficient use of fixed preferences as a draw criterion.

One embodiment of the present invention comprises a computer program system using a filtered priority row for the manufacture of planning and scheduling systems having entities representing orders for products. The orders consist primarily of a part number, quantity, and deadline date and are associated with zero or more fixed preferences.

The fixed preferences, in this modality, comprise a set of functions that qualify the importance for a factory to meet the deadline date of each order. Fixed preferences may vary according to the priorities of each factory. In this mode the deadline date is used as one of the fixed preferences. An order that expires tomorrow must be preferred over an order that expires one month later, because there is time to make adjustments so that the last order can be accommodated. Another fixed preference used in this mode is the ordered quantity. Small orders can be preferred over large orders. An additional fixed preference used in this modality is a customer priority factor reflecting the customer's current attitude or the need for parts. An additional fixed preference used is the cost of manufacturing the product. It may be preferable to build those orders that are less expensive.

In a manufacturing environment, a material account comprises a list of the parts necessary to build the manufactured product. The order plans comprise all three of the construction parts according to the materials account and comprise the reservation of parts supplying any parts that are not constructed.

In a manufacturing environment, the fixed preferences used according to the teachings of the present invention to filter and sort out the priority row are determined from the manufacturing objectives. Planning for a factory involves a process to develop order plans and manufacturing programs. A plan can schedule some late orders because the inventory of parts is not always enough to satisfy the plans of all orders. Planning can have several formulas for objectives, but generally the objective is to minimize the number of late orders or the delay of the total order.

The present invention provides advantages in the prioritization of orders received by a factory. When comparing two orders for the same part, it may be more critical to plan that one having higher values for all of your fixed preferences. For example, a first order may be preferred over a second order if the first order has an earlier due date, a smaller quantity and a higher customer priority. However, if the second order has a higher client priority, then neither of the two orders is necessarily preferred over the other. A filtered priority row is constructed using these relationships according to the teachings of the present invention.

In this modality having entities representing manufacturing orders, the fixed preferences can be based on the expiration date, the quantity and the customer's priority factor. The order having a more anticipated expiration date must be planned first to reduce the opportunity of not meeting an expiration date due to a lack of inventory or a machining capacity. The order taking a smaller quantity is the easiest to satisfy and must be planned first. Plans are often more productive in terms of satisfying order quantities and due dates when smaller orders are filled first. In addition, when resources are scarce, the satisfaction of multiple small quantity orders may be preferable to satisfying a large quantity order because more customers are satisfied. This, of course, may depend on the planning objectives. Finally, the order must be planned first with a higher customer priority factor. In the comparison of these two orders, if a client is rated as more important, then it is better to assign that client the scarce inventory on the assignment to another less important client.

A "same part" restriction can be useful as a fixed preference identifying orders for the same part. Orders for the same part require the same resources and inventory even when in different amounts. It is difficult to know when a first order that expires in a week must be planned before a second order that expires in two weeks and the two orders are for different parties. The second order can have a long manufacturing time so that it requires resources before the first order. On the other hand, if the first order and the second order are for the same part, the first order is known to require resources before the second order. A "same part" restriction provides an indication of which orders should be comparable in terms of fixed preferences because the orders have the same manufacturing process.

In this embodiment of the present invention, a priority row having a relatively large number of entities each representing orders is filtered and sorted to determine the most critical order. This determination of the most critical order is made more efficient by filtering the orders according to the teachings of the present invention. A priority row is created for each end item part in the manufacturing environment. Each priority row is then populated with entities representing the orders for each part requiring planning or programming. Each priority row is filtered to produce a filtered priority row having a network comprising a filtered game and a remaining set of commands according to the teachings of the present invention. The orders in the remaining game of the network heads do not have orders preceding them and are the most valuable ones to consider in order to plan or be programmed immediately as the most critical orders. The next order processed is the most critical order depending on the defined lottery criteria. The processing efficiency is greatly increased according to the technical advantages of the present invention because only those orders in the remaining game are drawn. The remaining game is always equal to or smaller in number than the total number of entities in the priority row. After an order in the game is processed before, the order is removed from the filtered priority row. The priority row is then refiled and the remaining game is drawn again.

A technical advantage of the present invention is the large reduction in the number of orders that must be compared to choose the next order to plan or program. At any given time, fewer orders should be compared than with conventional priority row drawings. The general update load of the filtered priority row network is small compared to the potential computations required to compare all orders to bypass the full priority row.

Although the present invention has been described in part with reference to a computer program system used to program a manufacturing operation, this embodiment is described only for purposes of teaching the advantages of the present invention. The present invention benefits any computer program system using a priority row to bypass entities. In particular, the present invention benefits systems that plan and program machines, tools, work gangs, resources, addresses, address operations or any other entity present in a planning or programming problem.

Although the present invention has been described in detail, it should be understood that various changes, substitutions and alterations may be made thereto without departing from the spirit and scope of the invention as defined in the appended claims.

Claims

R E I V I N D I C A C I O N S

1. A priority row filtering system comprising: an operable filtering module for accessing a plurality of entity data records of a priority row, and further operable for filtering and arranging the data records in a memory storage device for forming a filtered priority row, the filtered priority comprises; a filtered game containing a first subset of data records, the first subset of data records form sub-levels of a network; Y a remaining game containing a second subset of data records, the second subset of data records comprises network network heads; Y a draw module coupled to the filtering module, the draw module can be operated to access the remaining game, and it is also operable to order record data in the second subset of data records to identify data records of a more critical entity .

2. The system as claimed in clause 1, characterized in that the first subset of data records and the second subset of data records are filtered by the filtering module according to a plurality of fixed preferences associated with each data record. in the first and second subsets of data records.

3. The system as claimed in clause 2, characterized in that the second subset of data records is ordered by the draw module according to the plurality of fixed preferences.

4. The system as claimed in clause 3, characterized in that the second subset of data records is further ordered by the draw module according to additional criteria.

5. The system as claimed in clause 3, characterized in that the plurality of fixed preferences associated with each data record in the first and second subsets of data records is associated with a single task represented by each data record.

6. The system as claimed in clause 1, characterized in that a single task represented by each register gives data in the first and second subsets of data records comprises planning an order for a product manufactured by a factory.

7. The system as claimed in clause 6, characterized in that the first subset of data records and the second subset of data records are filtered by the filtering module according to a plurality of fixed preferences associated with each data record. in the first and second subsets of data records.

8. The system as claimed in clause 7, characterized in that the second subset of data records is ordered by the draw module according to the plurality of fixed preferences.

9. The system as claimed in clause 8, characterized in that the second subset of data records is further ordered by the draw module according to the additional criteria.

10. The system as claimed in clause 8, characterized in that the plurality of fixed preferences associated with each data record in the first and second subsets of data records is associated with the order planning for a product manufactured by a factory represented by each data record.

11. The system as claimed in clause 10, characterized in that the fixed preferences comprise an ordered quantity, a due date and a customer priority factor associated with the order for a product manufactured by a manufacturer.

12. A method for filtering and sorting a priority row having a plurality of entity data records, comprising: filtering the plurality of data records to build a network interrelating the plurality of data records using a plurality of fixed preferences associated with each data record; storing and arranging the plurality of data records in a memory storage device according to a structure of the network; identifying a remaining set of data records comprising network heads and identifying a filtered set of data records comprising sub-levels of the network; Y bypassing the remaining set of data records to determine data records of a more critical entity.

13. The method as claimed in clause 12, characterized in that the draw step further comprises sorting out the remaining set of data records according to fixed preferences associated with each data record.

14. The method as claimed in clause 13, characterized in that the draw step further comprises circumventing the remaining set of data records according to additional criteria associated with each data record.

15. The method as claimed in clause 12, characterized in that it further comprises the step of selecting the plurality of fixed preferences associated with the plurality of data records before the filtering step.

16. The method as claimed in clause 13, characterized in that it comprises the step of quantizing and storing the plurality of fixed preferences associated with each data record after the selection step.

17. The method as claimed in clause 13, characterized in that the filtering step includes using fixed preferences associated with a single task represented by each data record.

18. The method as claimed in clause 17, characterized in that the single task represented by each data record comprises planning an order for a product manufactured by a factory.

19. The method as claimed in clause 18, characterized in that the plurality of fixed preferences associated with each data record is associated with the order planning for a product manufactured by a factory.

20. The method as claimed in clause 19, characterized in that the fixed preferences comprise an ordered quantity, a due date and a customer priority factor associated with the order for a product manufactured by a factory.

21. A method for processing a priority row having a plurality of data records, each representing a single task, comprising the steps of: filtering the plurality of data records to build a network interrelating the plurality of data records using a plurality of fixed preferences associated with each data record; storing and arranging the plurality of data records in a memory storage device according to a network structure; identifying a remaining set of data records comprising network heads and identifying a filtered data record set comprising sub-levels of the network; raffle the remaining set of data records to determine a data record of a more critical entity; remove the data records of the most critical entity in the memory storage device; carry out the unique task represented by the data record of the most critical entity removed in the removal step; and repeating the steps of identification, drawing, removal and realization until each data record in the plurality of data records is processed.

22. The method as claimed in clause 21, characterized in that the single task represented by each data record comprises planning an order for a product manufactured by a factory.

23. The method as claimed in clause 22, characterized in that the plurality of fixed preferences associated with each data record is associated with the order planning for a product manufactured by a factory.

24. The method as claimed in clause 23, characterized in that the fixed references comprise an ordered quantity, a due date and a customer priority factor associated with the order for a product manufactured by a factory. SUMMARY A priority row filtering system is provided. A filtered priority row comprises a remaining game and a filtered game. The filtered game contains a first subset of data records. The first subset of data records forms sub-levels of a network. The remaining game contains a second subset of data records. The second sub-game of data recording comprises the network heads of the network. A draw module is coupled to the filtering module. The draw module is operable to access the remaining game and is further operable to order the data records in the second subset of data records to identify a data record of a more critical entity.