Manufacturing a "Whatcha-ma-callit"
Project 3 Version 1.0
CS2704, Summer I 2002
Due: 8:00 AM, Wed. June 26
Additions after version 1.0 appear in the color of the date they were made. Deletions are also in the color of the date they were made and appear in
Discrete Event Simulation
Computerized simulations are representations or imitations of real-world processes or activities. Some simulations are termed discrete event simulations because the simulation is divided into discrete steps corresponding to an "event." For example, an arrival of a new simulated object or the end of a simulated time interval would be an event. At each discrete step the new state of the simulation is computed.
Discrete event simulations simulate time itself. Events are added to an ordered list according to the time at which the event occurs. The simulation reads events off the list, updates the simulated time to match that of the event, and processes the event. In this way, the simulation can make large leaps in time. Therefore, a discrete event simulation potentially executes more quickly than a simulation that runs in real-time.
This assignment simulates a manufacturing process of a ‘Whatcha-ma-callit’. Now, a whatcha-ma-callit is made from a single ‘thing-a-ma-gig’ and a single ‘do-hickey’. Of course, a ‘thing-a-ma-gig’ is made of 3 smaller components (the names get too confusing here, so we’ll name them Parts A, B, and C), and a ‘do-hickey’ is made from 4 smaller components (call them W, X, Y, and Z). Figure 1 illustrates the system.
Creating a ‘thing-a-ma-gig’ will be referred to as the first process; creating a ‘do-hickey’ will be referred to as the second process; the third process is putting together the ‘thing-a-ma-gig’ and ‘do-hickey’ into a ‘whatcha-ma-callit.’ ‘Thing-a-ma-gigs,’ ‘do-hickeys,’ and ‘whatcha-ma-callits’ are referred to as composite components or objects in this discussion. Individual components (A, B, C, D, W, X, Y, and Z) are also called pieces. The order of steps for each process is:
And, of course, while one object is being combined, others can be checked and decomposed. All of these units can be operating simultaneously.
Description of Components
So, you can see that the system is made up of three different types of units (combinators, checkers, and decomposers). Since there are three different processes with these 3 units, there are nine different units. Each unit can be turned on and off, and each unit has a different (constant) completion time. When the system "starts," all of the units are off. For example, the combinator unit for process 2 might take 6 minutes to complete and is currently shut off. (Input will turn units on and off, as well as add components to conveyor belts that feed components to units.)
Each of the 3 combinator units (1 for each process) takes a fixed number (read from the input file) of each of its sub-components to form it, e.g. a ‘do-hickey’ might be made up of 2 Ws, 4 Xs, 1 Y, and 2 Zs. These are combined to form one ‘do-hickey.’ Each sub-component/piece (A, B, C, W, X, Y, or Z) has a quality assigned to it; the quality of a composite component (a "thing-a-ma-gig," "do-hickey," or "whatcha-ma-callit") is the average of the qualities of its sub-components.
The 3 checker units (1 for each process) examines the new composite object to make sure that its overall, average quality meets its standards, i.e. a component’s quality is greater than or equal to some threshold, which is a constant, specified value. Each checker has a different threshold; these are specified in the input file. Either a particular object passes a checker (has a quality >= to that checker’s threshold) or fails (has a quality less than the threshold). If a composite object passes, then the object continues to the next combinator’s conveyor/queue or finishes the manufacturing process. If it fails to pass the checker, then it is sent to the appropriate decomposer unit’s conveyor/queue for that process. Checking an object takes a few minutes; the amount of time is specified in the input file. For Checker 3, the quality of the component (a Whatcha-ma-callit) is the average of its 2 component parts.
The 3 decomposer units (one for each process) take an object and break it down into component parts. Decomposer units for processes 1 and 2 break the object into the base pieces by putting the pieces into the appropriate conveyors/queues, whereas the decomposer unit for process 3 only breaks the object into process 1 and process 2 composite objects ("thing-a-ma-gigs" and "do-hickies"). During decomposition within processes 1 and 2, the base components are further checked (further with regard to what the checker looked at) against 2 additional standards:
Otherwise the base components are put into the proper component’s conveyor/queue. When a piece is thrown out, it must be put into a Dumpster object, which is another queue that is displayed at the end of the program. Note that Decomposer 3 does not do these additional tests. The time it takes a decomposer to do its job is specified in the input file. NOTE: The relative order of the base components must be maintained!!! For that reason you must use queues to hold the components.
Each of the 9 units (3 combinators, 3 checkers, and 3 decomposers) has a time associated with it that is the amount of time it takes for that unit to complete its job These 9 values are read from an input file, whcih is specified below.
Also, each Checker has a threshold value associated with it, e.g. .77, that defines how high the quality of a composite object must be in order for it to "pass" the checker and move onto the next combinator (or out of the process). These 3 threshold values are also in the input file.
Finally, a combinator puts together several pieces (or composite objects, in the 3rd process) to make a composite object. The number of each of these sub-components is also specified in the input file. For example, the input file might define a Whatcha-ma-callit as made up of 2 Thing-a-ma-gigs and 1 Do-hickey.
It should be clear that some of the units are slower than others and will cause bottlenecks in the system. A bottleneck is a point in a process, or unit in this case, where "things" are being slowed down or even halted. Further note that each of these 9 units can be turned on and off. When a unit is turned off, it will probably also cause a bottleneck. A bottleneck causes the units after the bottleneck not to have the components it needs to continue, which is a bad thing.
An important aspect of this project is the conveyor belts between these "units." These conveyor belts between manufacturing stations must be implemented as queues in order to maintain the order of the pieces/components. The units themselves only "hold" onto some sub-components while they are working on the components, basically how long it takes before moving a component into the next conveyor/queue. This project simulates Whatcha-ma-callit production by having components move around from queue to component, to queue, to component, to queue, etc. For example, when a component such as an A is added to the system, it is enqueued in the first queue in the diagram. Once there are sufficent components in each of the queues before Combinator 1 and Combinator 1 is ON, then Combinator 1 dequeues enough of each of the components as specified in the input and holds onto them until the combinator is done with them (how long this takes is in the input file), then it enqueues them onto the queue before Checker 1. As soon as Checker 1 has a composite object in its queue AND it is turned on, it dequeues a composite object and holds it for however long is specified in the input for Checker 1 (as though it is checking it). Similarly for all of the other queues and units.
It is important to understand that you are simulating time itself, such that at time 106, for example, your program needs to perform all of the actions that are supposed to occur at time 106. This is because at time 106 Combinator 1 and Checker 2 and Combinator 3 could all have something to do (such as start or end its "work"). This is completely different from the first project in which the system clock actually made actions occur in your program.
The input file contains unit parameter information at the beginning of the file for all 9 units. The first line contains information for Process 1 (i.e. Combinator 1, Checker 1, and Decomposer 1); the second and third lines contain infomation for Processes 2 and 3, respectively. For example, the first 3 lines of input might look like the following:
3 2 5 .77 2 1 2
6 3 3 .70 1 1 3 4
4 6 4 .80 2 1
This would indicate that Combinator 1 takes 3 minutes, Checker 1 takes 2 minutes, Decomposer 1 takes 5 minutes, Checker 1 has a threshold of .77 (77%), and Combinator 1 combines 2 As, 1 B, and 2 Cs to make a Thing-a-ma-gig. Similarly for the suceeding 2 lines.
After the parameter information, the remainder of the input contains instructions to add pieces to the piece queues (on the left side of the diagram), turn units on and off, and perform system functions (which are described later).
Each input line is a "command;" the first number on each line is the time when the command-event should occur. The time is always an integer number and the manufacturing process starts at time 0; therefore, all events in the input are positive integers that occur at the specified time after manufacturing starts. In the input, C represents Combinator, K represents Checker, and D represents Decomposer; the numbers indicate which process they are associated with. For example, the first line of the input could be
33 + C1
which would mean that at time 33 Combinator 1 is turned on (+). There are 6 types of input events:
502 P W 1023 .66
which indicates to add a Piece at time 502 to the W queue with an identifier of 1023 that has a quality of .66. So, the general form of adding a piece is
time P piece-queue identifier quality
Time will not be larger than an int; identifier will be a 4-digit number not beginning with a zero; and quality is a floating point number between 0 and 1.
A system report (#2 above) prints the same information as the final report and is described below. An example event of generating a system report is
A unit report (#3 above) prints information for a particular system unit. An example event generating a unit report is
200 U D3
An example of #4 above is
which would turn on Checker 2 at time 400. Note that turning on a unit that is already on does nothing, it simply indicates that the unit is now on. If a unit is "busy" at the time it is turned off, then the unit is "turned off" but allowed to complete the work it is engaged in; it will not re-fill once it completes its work because it is turned off. This can be implemented in a number of ways, but the idea is that the unit completes its work in progress; it does not actually stop, if it is busy when it receives a "turn off." An example of #5 is
which would put the system on hold at time 245 until the user (a real person) hits return at the keyboard (or presses a Resum button in a GUI). This implies that your program reads input from the file that is indicated on the command line, but your program also reads input from the keyboard for H events. The final type of input in the file is the Stop "command" event:
which ends the simulation and prints a "final" report of the system, described in the Output section. This implies that you need to keep track (in another queue) of all of the completed components.
Input should be assumed to be infinitely long. This means that you may not read in all of the input and then start processing. You can only read in one input at a time. Once you have performed that event, then you should read in the next input event. Note that the times on the events do not have to be unique; more than one input action can occur at the same time. The input times are guaranteed not to decrease, i.e. go backwards in time. For example, a valid input could consist of the following:
200 U D3
200 + C1
200 + K2
205 + D2
Note that the input will have exactly one space between each item on the input lines.
Your executable program must be called proj3.exe. It must accept 2 command line arguments for the input file and output file. e.g.
proj3 infile1 outfile1
infile1 will contain the unit parameter information and input events.
The input file format is guaranteed to be correct, although you must check that you are getting an acceptable input command. All data is space delimited, and all fields are guaranteed to be present on each line, i.e. the input won't have something like just
without a unit on the line.
Output will consist of a graphical display as well as output to a file. The exact file output for each input "command" event will be provided, along with some sample input and corresponding output. You output must exactly match the provided output for grading purposes. (We want to be able to automate the grading somewhat.) The generated output should be sent to a file specified on the command line, as described above. This text output to a file can be extremely useful in debugging, if you set up useful test situations. This file will contain output for:
The unit information is also what should be printed for a ‘U’ command.
Notice in the above description that you need to print identifiers for the component objects. The input provides identifiers for pieces; you must generate identifiers for all composite components. Begin numbering Thing-a-ma-gigs with 10000 and increment by 1 in the numbering; begin numbering Do-hickies at 20000, also incrementing by 1; begin numbering What-cha-ma-callits at 50000.
Note: If you print additional information (debugging info, for example), make sure that this is removed or turned off for your final executable (what you turn in).
In addition to the events specified in the input file, your simulation will generate events. For example, one system-generated event is "CheckToFill," which tells the system to check if the input queues for a combinator have enough pieces available and the combinator is not busy, if so fill the combinator. More generally, whenever a piece is added to a unit's queue (or a component is removed from a unit), the simulation should add a CheckToFill event (for the next unit in the process) to the event list at the same simulated minute. For example: if a piece of type A is added at time 100, a CheckToFill event should be generated for Combinator 1 at time 100.
As another example, when a combinator has all of the pieces it needs, the simulation should generate an event to have the combined piece removed after the combinator’s designated amount of time. For example, suppose combinator 1 has all of its requisite pieces at time 894, then the simulation should generate an event to Remove the combined-piece from combinator 1 at time 897 (assuming that it takes 3 minutes for Combinator 1 do perform its action).
Here is a list of event types that the simulation should handle.
I. Input (not ordered/prioritized)
· Load in a piece from input (P)
· Change a unit’s status to/from on/off (+/-)
· Perform a system report (R)
· Perform a Unit report (U)
· Hold the system until input (H)
· Stop (exit) the program at current time (S)
II. Internal Events
· Remove piece from Combinator 1
· Remove piece from Combinator 2
· Remove piece from Combinator 3
· Remove piece from Checker 1
· Remove piece from Checker 2
· Remove piece from Checker 3
· Remove piece from Decomposer 1
· Remove piece from Decomposer 2
· Remove piece from Decomposer 3
· CheckToFill Combinator 1 with pieces
· CheckToFill Combinator 2 with pieces
· CheckToFill Combinator 3 with pieces
· CheckToFill Checker 1 with pieces
· CheckToFill Checker 2 with pieces
· CheckToFill Checker 3 with pieces
· CheckToFill Decomposer 1 with pieces
· CheckToFill Decomposer 2 with pieces
· CheckToFill Decomposer 3 with pieces
You might notice that frequently more than one of these events occur during a given minute, e.g. time 111. You need to enact all of the events at time X before incrementing the "time." New internal events that are generated should be added after events at that same time that are already in the event list. For example, if there are already 3 CheckToFill and 1 Remove events in the event list at time 104, and you need to add another event (like another Remove), then you add the new Remove after the existing 3 CheckToFill and 1 Remove events.
All input commands for a given "time" must be performed before any internal events at that time. Further, each line of input should be read in one at a time and "processed" before the next line is read in. In other words, the input can not be sorted for each time, nor can all of the input be read in and put into the event list. One way to implement this will be discussed in class.
There are some classes that clearly need to be defined for this project. Here are a few that are readily identifiable. Some of these are data types with which you are familiar and should be implemented immediately.
Obviously, you need queues objects. Some suggested queue methods include: Queue(), ~Queue(), IsEmpty(), Enqueue(), Dequeue(), Front() or Peek(), Display(), Count(), etc. The queue module should not manipulate the information within each of the nodes that it stores, other than necessary links for queue methods. The "information" being stored in the queue should be of no concern to the queue functions. So, you probably want a Node class too.
An event object is important to the execution of the simulation because you must maintain a list of actions to be performed. See the Event List and Driver classes below.
An event list will need to be maintained. Frequently people refer this as an event queue, but strictly speaking, it has to be a list in which events can be inserted into the middle of the list into its proper time placement in the list. A queue, strictly speaking, can only be enqueued into the rear and dequeued from the front.
This is the overall controller of the program. It will probably read input, manipulate the eventlist, and communicate with the Process Objects.
To properly model the entire Whatcha-ma-callit process, there should be a Process object that reflects the three processes as shown in the figure. Process 1 creates thing-a-ma-gigs; process 2 creates do-hickies; etc. The Process Object might move the created objects between the units, making the units not need to know a higher level of the overall process (information hiding). This also allows the process to be changed without having to change the individual units, queues, etc.
Pieces, Thing-a-ma-gigs, Do-hickies, and Whatcha-ma-callits
Clearly the "things" being "produced" by the simulation need to be objects.
Objects need to be definded to represent the units performing the work in the simulation.
The implementation details are left to you. For your design, you may need any number of other objects to implement the simulation in the way that you see it (and design it).
This project will be graded based on the following scales. Similar to the second project, the given percents are the maximum that you can achieve if you complete the listed functionality. For example, if you complete 80% of the project, then you will be graded with 80 being a maximum. If you didn’t provide satisfactory documentation, for example, then you might lose 5%; therefore you would get a 76.
Start Early! Time is your enemy!
Two words: incremental development. See the class web page for a description of what this is all about and why you want to do it.
Queues are critical to this project. You can implement the class immediately. You can code and test it tonight. Make the class general; build it to work for integers, then once you figure out what exactly your piece and component classes look like, you can change the type in the nodes to be classes.
Another part of the project that can give some people difficulty is the input, although Project 2 should have helped you learn this. This too you can work on immediately; you know the input format. Write a read_command() function immediately, and test it!
The structure of the processes is similar; the primary difference is the timing delays. Use incremental development. Get the input read in properly, then focus on the first process, and soon the others will fall out.
Do class diagrams. Some class discussion and question answering will occur for a week or so after this assignment is handed out. Class attendance will be imperitive during this time. This document is fairly complete on what the simulation is supposed to do; don’t delay starting this project.
Write debugging functions to help in your development. Functions such as print_unit(), print_q(), etc. are incredibly useful, although they are not specifically required for the assignment.
Set up test situations with the input. For example, you need to test what the simulaiton does if a component has a quality at exactly the threshold for a checker. Create the test data to test that right now! You should test for just above and just below the threshold too.