代写操作系统中的Assembly Line Scheduler. 由于作业是group作业，只需要完成其中一个part即可。
Scenario
Poly-Comp Factory owns 3 assembly lines for producing a number of products. On average, each assembly line can produce 1,000 products (no matter what they are) a day. For each product, it requires the usage of different pieces of equipment to assist the production process. For example, Product_A needs Equipment_1 and Equipment_4 while Product_B needs only Equipment_3 to produce the final products. Recently, the factory manager found that quite a number of Orders could not be completed on schedule and the profit of the company was falling. For example, there was an Order for Product_A, but it was found that Equipment_1 was not available before the production because the required equipment was still in use to produce Product_E. Moreover, the capacity of the three assembly lines was not fully utilized according to company’s financial reports. Knowing that you have learnt algorithms about the “scheduling” in the Department of Computing, would you mind helping the company to address the problem?
In this project, we assume that there are only 5 different products (Product_A, Product_B, Product_C, Product_D and Product_E) to be produced and, 8 pieces of equipment (Equipment_1, , Equipment_8) to be used with the three assembly lines during the productions. You are asked to help the company to schedule the Orders in production as well to demonstrate that the assembly lines and pieces of equipment could be used in an efficient way.
Project Requirements
Indeed, it is an opportunity to apply the theory of process scheduling which you have learnt from COMP2432 to a daily-life scenario and to create a Schedule. This project consists of four parts:
Part 1
Write a program that allows user to add details of an order or a list of orders (Order_Number, Product_Item, Equipment_Item, Order_Quantity, etc) to the scheduler, ALS. This is referred to as the Input Module.
Part 2
Extend your program developed in Part 1 with a scheduler to generate a production schedule. The scheduler may implement different scheduling algorithms (for this project, at least two algorithms are implemented) which are similar to those covered in lectures. However, the “First Come First Served” (FCFS) must be included, which is the simplest and could be used as a yardstick for comparison among the produced schedules. For the other one, you may choose any but it should show an improvement (by comparing to the FCFS). This is the Scheduling Kernel, contained within Scheduling Module.
Part 3
In addition, to assist management to know more about the improved schedules, the program should provide facilities to print out the Schedules of each Assembly Line which produced according to the algorithms in Part 2. This is the Output Module.
Part 4
Provide the program with the ability to generate an analysis report for the results produced in Part 3. Combine and compare the different Schedules produced and, show all the improvements. That is, for the one you have chosen to implement, it should have a better performance than the one based on FCFS. By the way, a rejected list must be included in this report for those Orders that cannot be accepted. This final module is the Analyzer Module.
You must form a group of 4 to 5 (at most) persons for the project. The project must be implemented using programming language C and it must be successfully executed on ANY ONE of Linux Servers in the Department of Computing. You will have to specify to us on which Linux server your project would be executed (e.g. apollo, apollo2).
***** Note that "gcc" is the only compiler that we are going to use in this project. *****
Implementation
User Interface
This application simply uses the “command line interface” (CLI) to interact with users. A user inputs various commands to add/create Orders in the scheduler (ALS) through a command prompt. The input methods may look like the following (blue colored lines).
~~WELCOME TO ALS~~
Please enter:
> addOrder R0001 D001 D010 Product_A 5000
Please enter:
> addOrder R0003 D003 D009 Product_B 8000
Please enter:
> addBatchOrder batch_Order_01.dat
Please enter:
Please enter:
> runALS -PR n | printSchedule > ALS_Priority_01.txt
Please enter:
> runALS -FCFS | printSchedule > ALS_FCFS_01.txt
Please enter:
> printReport > ALS_Report_02.txt
Please enter:
> endProgram
Bye-bye!
Input Format
For the inputs, most likely they are all expressed in one command line and we assume that there are no errors for those input values and data types.
No matter whether inputs are provided line by line through the application interface or they are imported through an external file in plain text format, you are recommended to input events (orders) which exceed the capacity of the available day units in your testing so as to produce some rejected orders. You are also recommended to test for fewer orders to check whether or not the algorithms implemented have been working as expected. Testing is a very important process to verify and validate your program developed. Generating good testing cases is often a challenge.
| Command | addOrder |
|---|---|
| Syntax | addOrder [order number] [expected start date] [expected due date] [product required] [quantity required] e.g. addOrder R0001 D001 D010 Product_A 5000 |
| Use | It is to specify the details of an order, “R0001” is the order number; “D001” is the expected start date; “D010” is the expected due date; “Product_A” is the product to be produced; and, “5000” is the quantity to be produced. |
| Command | addBatchOrder |
|---|---|
| Syntax | addBatchOrder [name of the batch file] e.g. addBatchOrder batch_Order_01.dat |
| Use | To shorten the input time, the application allows user to prepare a text file to store multiple orders. It is simply to record multiple order lines in one text format file, however, it uses “.dat” as the suffix to indicate that it is a data file. |
| Command | runALS & printSchedule |
|---|---|
| Syntax | runALS -[algorithm] [parameter] printSchedule > [output file name] e.g. runALS -PR n printSchedule > ALS_Priority_01.txt |
| Use | For runALS -PR n, it is to start the application to generate the schedule with the algorithm specified (in the example “-PR n” means “priority without preemption”). |
| Command | printReport |
|---|---|
| Syntax | PrintReport > [name of the output file] e.g. printReport > ALS_Report_01.txt |
| Use | It is to print out a report for what you have done in [Part 4], the [Analyzer]. In general, it looks like a summary of each algorithm used in that application and have a comparison of each algorithm to indicate which algorithm would have a better performance. In addition, a rejected order list is included. |
| Command | endProgram |
|---|---|
| Syntax | endProgram |
| Use | Terminate the application and exit the program properly. |
To ease your work, we make the following assumptions and notes:
- One day is treated as one unit. Since we would use the Schedules for the planning of production, we simply use “Day 1”, “Day 2”, etc to represent the period of the Schedule. In other words, no calendar date is needed in this application. In addition, we would like to have a sixty-day planning schedule, i.e. D001 to D060.
- To fabricate a product, some pieces of equipment are required to work together with the assembly line.
- Order should have been completed on or before the “Due Date”. Otherwise, the order would be rejected. This is like a hard real-time requirement for the orders.
- There are many implementation methods for those modules. The “Scheduling Module” may be implemented as a separate process, in the form of a child process created by the parent via fork() system call. The “Output Module” can also be implemented as another separate process. The scheduler may also be implemented as a separate program. If the parent is passing orders details to a child scheduler, one should use the pipe() and associated write() / read() system calls. If the parent is passing information to a separate scheduler program, one could use the Unix shell “pipe” (denoted by “|”).
- If pipe() and fork() system calls are both used properly in the program, the maximum possible mark is 100%. On the other hand, if both system calls are not used in the program, only a passing mark (50% to 55%) would be awarded. Intermediate scoring will be given if only one system call is used, depending on the extent of usage.
- Do not hard code the product name and the required equipment in Table 1 in your program. As technology or requirement change, the list may get updated. They should better be stored in a configuration file, which will be loaded when the program is executed.
- Bonus score of 5% would be given if you can propose a better algorithm which is not the one of the existing algorithms taught in the class.
Output Format
The Schedule format may look like the one below. (It is just for your reference, no need to follow it exactly.) You should have your own version/design/concern of the Schedule.
Assembly Line 1
Algorithm: FCFS
Start Date: D001
End Date: D060
Total number of working days: 60 days
Order accepted: 37 orders
Day not in use: 20 days
Day in use: 40 days
Utilization: 66.7%
The table above shows the “Order Number”, “Start Date”, “End Date”, “Due Date” “Quantity Requested” and “Quantity Produced”. Here “End Date” is the last day of the production (most likely it should be before or same as the “Due Date”). Moreover, for each assembly line, it should have its own “Schedule”, i.e. there are 3 Schedules in total.
To summarize the schedules, there is an analysis report to combine the figures. And, the report may look like the following one.
***Summary of Schedules***
Algorithm used: FCFS
There are 96 orders scheduled in total. Details are as follows:
Assembly Line | Order Accepted | Working Day | Utilization
=========================================================================
==
Line_1 37 40 66.7
Line_2 39 53 88.3
Line_3 20 35 58.3
=========================================================================
==
***PERFORMANCE***
AVERAGE OF WORKING DAYS FOR THE 3 ASSEMBLY LINES: 42.7 DAYS
AVERAGE OF UTILIZATIOIN: 71.1 %
TOTAL WORKING DAYS OF THE 3 ASSEMBLY LINES: 128.0 DAYS
UTILIZATION OF THE 3 ASSEMBLY LINES: 71.1 %
It is necessary to print out the report for each algorithm individually.
Finally, an “Order Rejected List” is printed, which may look like the following one.
***Order Rejected List***
TOTAL NUMBER OF ORDER RECEIVED: 126
- ORDER ACCEPTED: 96
- ORDER REJECTED: 30
REJECTED ORDER LIST
==================================
.
.
R0101 D031 D040 Product_A 8000
.
.
.
There are 30 Orders rejected.
Above report formats are just for your reference, you should have your own design and considerations.
Error handling
Although the program does not need to check for the correctness of the syntax of the inputs, some other errors handling are required in the application. For example, it is possible that the input date is out of the “period range” entered. Correction should be taken place automatically.
Documentation
Apart from the above program implementation, you are also required to write a project report that consists of following parts:
- Introduction (Why do you have this project?)
- Scope (What operating systems topics have been covered in this project?)
- Concept (What are the algorithms behind?)
- Your own scheduling algorithm (if any)
- Software structure of your system
- Testing cases (How to test the correctness of your program?)
- Performance analysis (Discuss and analyze the performance of each scheduling algorithm you have implemented, and this could provide inputs when you design your own algorithms)
- Program set up and execution (How to compile and execute your project? On which Linux server would you like your project to be executed?)
- Appendix - copies/samples of schedules of the three assembly lines and the summary report.
Demonstration
The demonstration will be held in Week 11 (tentatively). Each group has 10 minutes to demonstrate the implementation of the scheduler. Please write down the names and student IDs of your group members on the COMP2432 Project Group Form which should be posted outside PQ821.
Otherwise, you will be assigned to a group randomly. Demonstration schedule/timetable would be released once all the groups’ details are collected. The demo time slot would be allocated to each group randomly.