CmpE Project 5: Time is Money Solution

Precondition

Note that this is an optional project that would replace your lowest project grade if it is in the range [0, 65]. In other words, if you are satisfied with your grades for the previous projects or they are all higher than 65, you do not have to submit any code. In addition, the maximum grade is 75 instead of 100 for fairness.


    • Introduction

“The time is the most valuable thing.” -Vinay Chhabra & Manish Dewan. Time is much more valuable for engineers since it is a natural constraint that can not be stopped and what engi-neers do is to fight with constraints.

A food processing factory processes the raw materials sent by customers and turns them into the desired final product. There are two machines in the factory. These are the A and B machines. For a raw material to be converted into the desired final product, it must be processed in A and B machines at certain predetermined times depending on the properties of the product. This process takes place sequentially. Machine A takes the raw material and turns it into an intermediate product, while machine B transforms this intermediate product into the final product. The raw material is perishable before entering machine A, so it must be sent to the factory by the customer exactly at the time it should enter the machine A. The intermediate product produced by machine A is not perishable and can be sent to the machine B at any time to be processed.

The factory has received an order. In this order, the names of the requested products, the time required for the raw material to be spent in the A and B machines to convert the products into the final product, and the profits to be obtained from the products are written respectively. Factory engineer is a smart person with good time management. S/he listed all these jobs as the shortest time from the beginning of the first job to the end of the last job. According to this list, s/he determined the start time of each job. S/he also determined the time when all


1

jobs will be done. S/he sent these start times to the customer so that they could send the required raw materials exactly at that time, and the end time was the deadline for the contract to be made. The customer found these deadlines appropriate, and the contract was made. If the factory cannot grow a product within the specified deadline, it cannot receive the money it should receive for this product.

After the contract was signed, inspectors from the Ministry of Environment and Urbaniza-tion came to the factory. Investigators inspected machines A and B and sealed them as they were not environmentally friendly. The factory, which will no longer use these two machines, has bought a new machine that performs the work of these two machines on a single belt. This machine takes the raw material and turns it directly into the final product. The time taken for this process is equal to one of the times that the product must spend in machine A or B in the order list. If the product is a solid type, the total time taken for the new ma-chine to produce the product is equal to the time the product must spend in machine A in the order list; if the product is a liquid type, the total time it takes for the new machine to produce the product is equal to the time the product must spend in machine B in the order list.

The engineer examined the new machine and predicted that under these conditions, some of the products in the contract may not be grown within the specified deadline. Therefore, if it cannot grow all of them, it has decided to produce some of the products in a way that will maximize the profit of the factory. In this project, you are asked to calculate the maximum profit that the company can achieve in this case by looking at the order list given to you by the factory engineer.



    • Details

        ◦ For each case, output consists of one integer, int1 . It is is the maximum profit that the factory can gain after machine A and machine B are banned and new machine starts to process.

        ◦ Customers sends raw material on the day in the contract. Dates are determined according to times that products started to be processed on machine A. Raw material can not be sent before or after that time because of its perishable properties.

        ◦ Start and end times of the products that may be processed on the new machine are determined based on the type of products. Start time is always the time when raw material is reached to the factory.(It is actually starting time of the process on machine A for each product). End time is start time + X where X is machine A’s process time of the product if the product is solid otherwise machine B’s process time of the product.


    • Input & Output

3.1    Input

    • The first line represents the type of products respectively.


2

    • The second line represents the processing times of the products on machine A respectively.

    • The third line represents the processing times of the products on machine B respectively.

    • The fourth line represents the profit gained by factory by processing products respectively.

    • The fifth line represents the receiving times of each products according to the signed contract.

comment

Sample Input File
Explanations










s l s l l
Types of product1, product2, product3, product4, and product5 respectively. ’s’ means ”solid”, ’l’ means ”liquid”.
6210411
Minimum times are 6, 2, 10, 4, and 11 for product1, product2, product3, product4, and product5 on machine A

respectively.





37895
Minimum times are 3, 7, 8, 9, and 5 for product1, product2, product3, product4, and product5 on machine B

respectively.





105768
Factory gains 10, 5, 7, 6, and 8 profits if it produce product1,product2, product3, product4, and product5 respec-

tively.





2706216
arrival times are 27, 0 , 6, 2, 16 for product1, product2, product3, product4 and product 5 respectively.


Table 1: Sample Input with Explanations









Products

New Machine

Profits


Time in

Time out























1
27

33

10

2
0

7

5

3
6

16

7

4
2

11

6

5
16

21

8









Table 2: Possible processing intervals of products on new machine.

This table indicates jobs with start and end time. We already know profits of these jobs. After obtaining this table, problem is finding maximum profit job schedule. Maximum profit is the second line of the output.

3.2    Output

1. An integer representing the potential maximum profit of the factory.


Output File
Explanation


25
Maximum profit of factory after A and b machines are banned and new machines processes.

Table 3: Expected Output File and Explanation of each Statistic












3

3.3    Pseudocode about dynamic programming to find the maximum profit




Algorithm 1 Find Maximum Profit


Parameters

offers: list of objects containing start time, end time, and profit of each order. It is sorted based on end time

totalOffer: total number of offers

    1: maxProfit ← [0]*totalOffer

    2: for iteration = 1, 2, . . . , n do

    3: j ← iteration -1

    4: while j >= 0 and offers[j - 1].endTime > offers[i - 1].startTime do

    5: j ← j-1

    6: end while

    7: maxProfit[i] ← max(maxProfit[i-1], maxProfit[j] + offers[i-1].profit)

    8: end for

    9: return maxProfit[n]




3.4    Java Project Outline

Your java project will be named Project5. Your entry class for the project will be named project5main. All your .java files will be under folderProject5/src. Your project should be compatible with Java 16. Your program will be compiled with below command:


javac Project5/src/*.java -d Project5/bin –release 16


The input and output files can be at any folder. Design your code in order to accept full path for file arguments. Your program will be run with below command:


java project5main <inputfile> <outputfile>


Make sure that your final submission compiles and runs with these commands.


    • Grading

Grading of this project is based on the automatic compilation and run and the success of your code in test cases. If your code compiles and runs with no error, then you will get 5/75 of the project grade. The rest of your grade will be the sum of collected points from each test case. Maximum project grade is 75. If your submission is not auto-runnable, then you will receive 0 at first and then have to issue an objection.


    • Warnings

        1. This is an individual project.

4

    2. All source codes are checked automatically for similarity with other submissions and exercises from previous years. Make sure you write and submit your own code. Any sign of cheating will be penalized and you will get -50 points for the project.

    3. There will be a time limit on test cases, so it is important to write your code in an efficient manner.

    4. You can add as many files as you can as long as they are in the “src” folder and your project can be compiled as above. But the entry point of your program should be “project5main.java”.

    5. Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment, or make your variable names unnecessarily long. This is very important for partial grading.


    • Submission Details

You will zip up your project folder and submit on Moodle as a single .zip file. The name of the zip file isCmpe250 Project5 <studentid>.zip No other type of submission will be accepted.









































5