20-CS-122-001 | Computer Science II | Spring 2012 |
---|---|---|
Homework Assignment 3 |
Assembly Line Scheduling
Due: April 26, 2012
(submit instructions: here)
This homework exercises your ability to use classes and think recursively. A
reasonable solution is ridiculously short and yet the problem is one of the
most important we will encounter in Computer Science.
A factory which produces complex machinery on a single assembly line may need to take some care in planning which subassemblies or components are completed at what point on the line. For, if a component type is scheduled for completion after it is supposed to be installed then a problem will certainly exist. The problem is compounded by the fact that duplicates of the same component type may be used many times in assembling other components which themselves may be used many times and so on.
We wish to find an order of assembly of components on a single production line so that no component requires a subassembly that has not been built earlier in the line. We again turn to graphs to help devise a solution. Use a vertex (a circle on a piece of paper) to represent a component type. If one component type, call it A, requires another, say B, then draw a line between the two circles representing type A and B with an arrowhead pointing in the direction of the B vertex. The arrow tells us that we cannot build A components before we build B components. In other words, we say A is dependent on B. For example, in the following picture
no component can be built before E or D components are, A components must wait until D and G components are completed, and so on. If the component assemblies are scheduled in the following order (left first)
E, G, H, B, F, D, A, C, I, Jthen all the components can be assembled successfully. By the way, a graph with arrows as above is referred to as a partial ordering of elements (in this case component types A through J) and an ordering such as the one above, where all dependencies are satisfied, is called a topological sort of the elements of the partial order (in this case, of components A through J). If the graph were such that for some vertex you could visit one or more other vertices by moving in the direction of the arrows, and then return to the vertex at which you started, then the graph is not a partial ordering and a topological sort is impossible.
Use classes in a meaningful way, to represent objects. Use
notions of recursion to simplify the search for the next object to be
output: each object will have a function that invokes a function of
the same name associated with each of its "neighbors" (as determined
by the arrows leaving it) and the purpose of the function will be to
insure all dependent objects are output before the current object is
output. Read input data from a file; make multiple passes through the
data file to avoid using constants to establish memory for data
structures.
Write a program to determine a topological sort of the elements of a
given partial ordering. This problem and an outline of the code you
can write are as follows:
Given a collection of n items and dependency lists for each item,
determine whether the dependencies support a topological sort. If not,
report this fact. Otherwise, find a topological sort of the vertices
with respect to the given dependency lists. A topological sort of the
items is a permutation of the items with the property that every item
in the permutation is to the right of all items in its dependency
list.
Given above.
input: A graph of vertices and lines with arrowheads in one direction
output: "Impossible" or a topological sort of the vertices
0. Create objects for each vertex 1. Set the state of each object to START 2. Install all the dependency lists for all vertices from file 3. For all vertices v execute topo(v) given below (imagine there is one copy of that code for each vertex)
topo:
input: A vertex v - invoked as topo(v)
1. Check whether v is in the DONE state 2. If so, return 3. Check whether v is in the ERROR state 4. If so, print "Impossible" and exit 5. Change v's state to ERROR 6. For all the vertices w in the dependency list of v do the following: 6a. Invoke topo(w) 7. Change v's state to DONE 8. Print "v" 9. Return
This Power Point Presentation
illustrates the action of the above method. In particular, 1) a
vertex in the START state is colored blue, a vertex in the
ERROR state is colored brown and a vertex in the
DONE state is colored yellow; 2) a black line with arrow from
one vertex (call it v) to another vertex (call it w)
means, in the context of the above method, execute line 6a; 3) if a
line is colored magenta, then that execution is in progress; 4) if a
line is colored green then that execution is completed.
class SubassemblyType { int state; // state for execution control char *ident; // String identifying this object SubassemblyType **depends; // Array of pointers to dependent objects int ndepends; // Number of dependent objects public: SubassemblyType (char *); // Constructor: sets ident, state void setdeps (SubassemblyType **, int); // sets dependency list, ndepends // Topologically sort from this object. This is accomplished by // topologically sorting the dependent objects first then outputting // the identity of this object. The variable "state" is used to // prevent the sort from occurring more than once and to detect // cycles, if they should exist. void topo (); };
... const int MAX_DEPENDS = 100; ... depends = new SubassemblyType*[MAX_DEPENDS];to make space for a dependency list. Instead use something like this:
... fstream fin; fin.open(argv[1],ios::in); ... for (int i=0 ; i < nobjects ; i++) setDependencies(fin, i, components);and setDependencies invokes components[i]->setdeps(...). This may require multiple reads of lines.
If the problem is understanding classes, see the lecture notes. If the problem is inputting, then embed the dependencies in the text of the code and do not worry about the input process right now. Otherwise, identify the problem to the grader or myself.