Help Identifying If Specific Problem is a Classical Comp Science Problem

Question

Hi All,

I have a manufacturing-process issue I tackled ages ago in VBA, and it's held up for some time now although it's progressively running slower and slower as more data gets into the file. I think it's finally time to rewrite a more elegant solution in a different language, outside of VBA, but am curious if anyone knows of this being a classical computer science problem and if it has been given an academic name so I can research a quicker algorithm.

I'll kind of outline it in point form below:

Say there exists different types of Widgets.... call them...

Widget-Type A

Widget-Type B

Widget-Type A has various serial numbers

Widget-Type B has various serial numbers

Furthermore,

You can tell what Type a Widget is (A or B) based on the serial number alone. Serial Numbers are appended a build-date (i.e. 2010-08-10)... if the serial exists but the date is missing, the Widget exists but isn't finished being built.

Widget-Type B can contain (one or more of) the parts from a Widget-Type A; therefore, Widget-Type B's serial number can have a list of sub-serial numbers from that of A.

Similarily, Widget-Type A can contain (one or more of) the parts from a Widget-Type B; therefore, Widget-Type A's serial number can have a list of sub-serial numbers from that of B.

Lastly,

There exists a Widget-Type C

Widget-Type C can only exist (be built) if given a Widget-Type A, that Widget-Type A has a build-date appended to the serial, AND all it's corresponding sub-serial numbers (from Widget-Type Bs) have build-dates appended to the serial.

Again, you can have the other case that Widget-Type C can only exist (be built) if given a Widget-Type B, that Widget-Type B has a build-date appended to the serial, AND all it's corresponding sub-serial numbers (from Widget-Type As) have build-dates appended to the serial.

As you can see, if Widgets A and B have many sub-serials, there's a lot of cross-checking and referencing going on to make sure a Widget C is produceable.

I know this was kind of a long-winded description, but any ideas if this is a variant of any common computer science problem?

Answer 1

I don't think this is the solution, but an idea to how you could solve this problem. Is it fair to assume that the problem is of a on ordered dependency? For Widget C to be produced, Widget A and Widget B need to be produced. And for Widget A to be produced, there might be a dependency on Widget B (and it is possible that there are cycles too, but with different values of the serial numbers of course).

Given the above, you can represent the widgets as an acyclic directed graph isn't it? The directed edge between two nodes (widgets) defines the dependency. For example, Wdget C <- {Widget A , Widget B}. Then you can use a topological traversal to get the right order of production.

Again, I am not sure if this is the answer you are looking for, but from what I understood from the problem definition, I think this is a possibility.