Scheduling Orders
1.1 General description
A Personal Computer Manufacturer invites you to design and implement a softwaresystem for production scheduling as part of their supply chain management system. Themanufacturer collects all the PC orders (an order bundle) from all their dealers at the endof a week. The order bundle is passed to you for you to schedule production for thecoming week. Your schedule is then forwarded to all the dealers and productiondepartment.
1.1.1 Products and components
The products to be manufactured are personal computers (PCs). Each PC model is builtfrom four components: CPUs, motherboards, memories and hard drives.
CPUs and motherboards are available in two different product families, Pintel and IMD.
A Pintel CPU only works with a Pintel motherboard, the same as IMD CPUs. CPUs areavailable in two speeds, 3GHz and 5.0 GHz, memories in size 4 GB and 8 GB, and disks
in sizes 1 TB and 2 TB. There are a total of 10 different components, which can becombined into 16 different PC configurations. Different type of PC requires a differentnumber of production cycles of production line. The catalogs of components and PCs aregiven in the following tables:
The running cost to produce each unit of a PC product is $100 per cycle. Therefore thetotal cost of a product is: the total cost of components + cycles*$100.
For instance, the cost of a unit of product no 7 is $3050:
• Pintel CPU 5 GHz: $1500
• Pintel motherboard: $250
• Memory 8 GB: $200
• Hard disk 2 TB: $400
• Running cost: 7*$100
1.1.2 Costumers orders
At the beginning of each week the manufacturer receives a bundle of orders from alldealers. Each order requires a single type of PC with order id, PC id, ordered quantity,due date, and unitProfit:
order = (orderId, PCId, orderQuantity, dueDate, unitProfit)
The quantity of each order ranges from 1 to 20. Due date could be any day betweenMonday-Friday (represented by integers between 0-4). Profit ranges from 15%-75% ofthe PC cost. Therefore the actual selling price of a product is:
unitPrice = unitCost + unitProfit
A product can be produced on or before the specified due date but if it is produced afterthe due date, a penalty of 10% of the product cost will apply each day it is delayed. Forinstance, if we have the following order:
orderId = 0;
PCId = 7;
orderQuantity= 19;
dueDate = 3 (Wednesday)
unitProfit = 1092
As calculated above, the total unit cost of product no 7 is $3050. The order gives a profitof $1092 each unit. Thus the selling price of each unit of the product is $4142. If theorder can be produced on or before Wednesday, the total profit from the order will be19*$1092 = $20,748. However, if the order was produced on Friday, the total profit willbe reduced to $20,748 – 2 days delay * 10% penalty * $3050 * 19 units = $9158.
If an order cannot be produced, a penalty of 50% of product cost will have to be paid.
For instance, if the above order is cancelled, a negative profit of the order will bereceived: -50% * $3050 * 19 units = -$28,975.
An order can be partially fulfilled. In this case, simply divide this order into two or moreorders with less quantity.
An order bundle is a set of orders (can be implemented as an array, a set or a vector oforder objects).
1.1.3 Manufacturing
The manufacturer is equipped with a PC production line, which has 2000 available
production cycles for producing all types of PCs. Running cost is $100 per cycle (no
fixed cost). Once you receive the order bundle, you need to schedule the production line
for the coming whole week to produce as many orders in the bundle as you can. There are
no inter-week orders, which means that scheduling is needed only once per week. The
scheduling needs to meet as many orders as possible because a penalty will be incurred at
10% of product cost per day for delayed orders. If an order cannot be scheduled for
production by its due date, it can be either delayed or canceled. Cancelling an order will
receive a penalty of 50% of product cost. A report needs to be produced at the completion
of the scheduling process. The report should include the following information:
The list of all satisfied orders (can be produced on or before the due date)
The list of all delayed orders (cannot be produced by due date but are able to be
produced within the scheduling week)
The list of all unsatisfied orders (unable to produce in the scheduling week)
The total components will be required for each day.
The total cycles will be used in each day.
A summary of all products scheduled for production in each day and total profit
will earn in the week after deducting penalty.
1.2 Tasks
Task 1: Extend the following Item class to two classes Component and Product usinginheritance (download Item.h from vUWS).
#ifndef ITEM_H
#define ITEM_H
class Item {
protected:
int id;
int cost;
public:
Item(){id = -1;} //the id for an empty item is -1
Item(int i) {id = i;}
int getId() {return id;}
int getCost() const {return cost;}
};
#endif
The data of component catalog (Table 1) and the data of PC catalog (Table 2)have been given in the provided Item.h file. You may move them to theComponent class and the Product class, respectively, for better abstraction.
Task 2: Create a class called Order that specifies customer orders. The class shouldinclude at least the data items: orderId, PCid, quantity, dueDate and unitProfit.
Task 3: Create a class called Schedule that performs the actual scheduling. The classtakes a bundle of orders as input from a text file, and outputs the schedulingreport. You can design your own format of the report but should include all theinformation specified above. The format of an order bundle is the following:
[orderId1, PCId1, orderQuantity1, dueDate1, unitProfit1]
[orderId2, PCId2, orderQuantity2, dueDate2, unitProfit2]
…[
orderIdn, PCIdn, orderQuantityn, dueDaten, unitProfitn]
Download an example of order bundle from vUWS to test your schedulingalgorithm.
Task 4: Create a class called BundleGenerator that simulates market demands of theproducts made by the manufacturer. The class should implements a memberfunction which is able to generate randomly an order bundle with about 150-250orders for any types of PCs (randomly generated), 1-20 PCs per order (randomlygenerated). The due date and profit are also randomly generated. The due daycan be an integer between 0-4 and the profit is a integer ranging from 15%-75%of the respective PC cost. The result should be written into a text file in theformat specified in task 3. Order id can be generated based on the ordinal of theorders in a bundle. Your scheduling program should be also able to accept abundle from the BundleGenerator object without going through writing andreading a file.
Task 5: Improve your Schedule class so that your schedule is detailed to each dayfrom Monday (day 0) to Friday (day 4) according to the dueDate informationspecified in each order.
Task 6: Calculate the total cost of production, the total penalty for delayed products andthe total profit will earn for the scheduled week.
Task 7: Implement separate classes or provide extra member functions of class Scheduleto optimize your scheduling in order to maximize the profit of the manufacturer.
You are only allowed to use C++ to code your solution. You can use any C++compiler or IDE to demonstrate your program provided it is available during yourdemonstration. You are allowed to demonstrate your program on your laptop.
Component.h
//Created by Dr Dongmo Zhang
#ifndef COMPONENT_H
#define COMPONENT_H
#include
#include
using namespace std;
#include “Item.h”
class Component : public Item {
private:
void setCost();
public:
Component():Item(){}
Component(int cid):Item(cid){setCost();}
string getName() const;
};
void Component::setCost() {
int costMap[] = {1000, 1500, 1000, 1500, 250, 250,100,200,300,400};
if(id<0 || id>9) {
cout <<“Component Id is out of range!” << endl;
} else {
cost = costMap[id];
}
}
string Component::getName() const {
string nameMap[] = {“Pintel CPU 3 GHz”,”Pintel CPU 5 GHz”, “IMD CPU 3 GHz”,
“IMD CPU 5 GHz”,”Pintel motherboard”,”IMD motherboard”,
“Memory 4 GB”,”Memory 8 GB”,”Hard disk 1 TB”,”Hard disk 2 TB”};
if(id<0 || id>9) {
cout <<“Component Id has not been initialized!” << endl;
return “”;
} else {
return nameMap[id];
}
}
#endif // COMPONONT_H
Item.h
//Crerated by Dr Dongmo Zhang
#ifndef ITEM_H
#define ITEM_H
const int cycleMap[] ={4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7};
const int compMap[16][4] ={{0,4,6,8},{0,4,6,9},{0,4,7,8}, {0,4,7,9},
{1,4,6,8},{1,4,6,9},{1,4,7,8}, {1,4,7,9},
{2,5,6,8},{2,5,6,9},{2,5,7,8}, {2,5,7,9},
{3,5,6,8},{3,5,6,9},{3,5,7,8}, {3,5,7,9}};
const string nameMap[] = {“Pintel CPU 3 GHz”,”Pintel CPU 5 GHz”, “IMD CPU 3 GHz”,
“IMD CPU 5 GHz”,”Pintel motherboard”,”IMD motherboard”,
“Memory 4 GB”,”Memory 8 GB”,”Hard disk 1 TB”,”Hard disk 2 TB”};
class Item {
protected:
int id;
int cost;
public:
Item() {id = -1; cost = 0;} // the id for an empty item is -1
Item(int i) {id = i; cost = 0;}
Item(int i, int c) {id = i; cost = c;}
int getId() {return id;}
int getCost() const {return cost;}
};
#endif
Solution
BundleGenerator.cpp
/*
* BundleGenerator.cpp
*
* Created on: Oct 11, 2017
*/
#include
#include
#include
#include “BundleGenerator.h”
BundleGenerator::BundleGenerator(stringbuf& p_buffer) :
m_sbuf(&p_buffer), m_os(&p_buffer) {
for (int i = 0; i < 16; i++)
m_products[i] = new Product(i);
}
BundleGenerator::~BundleGenerator() {
for (int i = 0; i < 16; i++)
delete m_products[i];
}
void BundleGenerator::generate(int p_num) {
srand(time(NULL));
m_sbuf->str(“”);
for (int i = 0; i < p_num; i++) {
int pcID = (rand() % 16); // pcID
m_os << “[” << i << “,” // orderID
<< pcID << “,” // pcID
<< (rand() % 20 + 1) << “,” // orderQuantity
<< (rand() % 5) << “,” // dueDate
<< int(
m_products[pcID]->getCost()
* ((rand() % 51 + 25) * 0.01)) // unitProfit
<< “]” << endl;
}
}
void BundleGenerator::save(const char* p_fname) {
ofstream ofile(p_fname);
ofile << m_sbuf->str();
ofile.close();
}
BundleGenerator.h
/*
* BundleGenerator.h
*
* Created on: Oct 11, 2017
*/
#ifndef BUNDLEGENERATOR_H_
#define BUNDLEGENERATOR_H_
#include
#include “Product.h”
using namespace std;
class BundleGenerator {
public:
BundleGenerator(stringbuf&);
~BundleGenerator();
void generate(int);
void save(const char*);
private:
stringbuf* m_sbuf;
ostream m_os;
Product* m_products[16];
};
#endif /* BUNDLEGENERATOR_H_ */
Component.cpp
/*
* Component.cpp
*
* Created on: Oct 11, 2017
*/
#include “Component.h”
const int costMap[10] = { 1000, 1500, 1000, 1500, 250, 250, 100, 200, 300, 400 };
const char* nameMap[10] = { “Pintel CPU 3 GHz”, “Pintel CPU 5 GHz”,
“IMD CPU 3 GHz”, “IMD CPU 5 GHz”, “Pintel motherboard”,
“IMD motherboard”, “Memory 4 GB”, “Memory 8 GB”, “Hard disk 1 TB”,
“Hard disk 2 TB” };
Component::Component(int p_id) :
Item(p_id, costMap[p_id]) {
}
const char* const Component::getName() const {
return nameMap[m_id];
}
Component.h
/*
* Component.h
*
* Created on: Oct 11, 2017
*/
#ifndef COMPONENT_H_
#define COMPONENT_H_
#include “Item.h”
extern const int costMap[10];
extern const char* nameMap[10];
class Component: public Item {
public:
Component(int);
private:
const char* const getName() const;
};
#endif /* COMPONENT_H_ */
Item.cpp
/*
* Item.cpp
*
* Created on: Oct 11, 2017
*/
#include “Item.h”
Item::Item(int id) :
m_id(id), m_cost(0) {
}
Item::Item(int id, int cost) :
m_id(id), m_cost(cost) {
}
int Item::getId() const {
return m_id;
}
int Item::getCost() const {
return m_cost;
}
Item.h
/*
* Item.h
*
* Created on: Oct 11, 2017
*/
#ifndef ITEM_H_
#define ITEM_H_
class Item {
protected:
int m_id;
int m_cost;
public:
Item(int);
Item(int, int);
int getId() const;
int getCost() const;
};
#endif /* ITEM_H_ */
main.cpp
/*
* main.cpp
*
* Created on: Oct 11, 2017
*/
#include
#include
#include “Schedule.h”
#include “BundleGenerator.h”
using namespace std;
int main(int argc, char* argv[]) {
stringbuf buffer;
if (argc < 2) {
BundleGenerator bg(buffer);
bg.generate(100);
Schedule schedule(&buffer);
schedule.process();
schedule.print();
} else {
ifstream ifile(argv[1]);
Schedule schedule(ifile.rdbuf());
schedule.process();
schedule.print();
}
return 0;
}
Order.cpp
/*
* Order.cpp
*
* Created on: Oct 11, 2017
*/
#include “Order.h”
Order::Order(int p_orderid, int p_pcid, int p_quantity, int p_duedate,
int p_unitprofit) :
m_orderid(p_orderid), m_quantity(p_quantity), m_duedate(p_duedate), m_unitprofit(
p_unitprofit), m_product(p_pcid), m_daymade { } {
}
int Order::getOrderID() const {
return m_orderid;
}
const Product* const Order::getProduct() const {
return &m_product;
}
int Order::getQuantity() const {
return m_quantity;
}
int Order::getDueDate() const {
return m_duedate;
}
int Order::getUnitProfit() const {
return m_unitprofit;
}
void Order::setDayMade(int p_day, int p_quantity) {
m_daymade[p_day] = p_quantity;
}
int Order::getMade(int p_day) const {
int sum = 0;
for (int i = 0; i < (p_day + 1); i++)
sum += m_daymade[i];
return sum;
}
int Order::getTotalCycles() const {
return m_product.getCycles() * getQuantityLeft();
}
int Order::getQuantityLeft() const {
return m_quantity – getMade();
}
int Order::getProfitPerCycle() const {
return (m_unitprofit / m_product.getCycles());
}
int Order::getDayMade(int p_day) const {
return m_daymade[p_day];
}
int Order::calculateProfit() const {
int profit = 0;
for (int i = 0; i < 5; i++)
profit += m_unitprofit * m_daymade[i];
for (int i = 1; i < (5 – m_duedate); i++)
profit -= m_daymade[(m_duedate + i)]
* ((0.1 * i) * m_product.getCost());
profit -= (m_quantity – getMade()) * (0.5 * m_product.getCost());
return profit;
}
OrderCompare::OrderCompare(const int& p_day) :
m_day(p_day) {
}
bool OrderCompare::operator()(const Order* lhs, const Order* rhs) const {
if (lhs->getDueDate() == m_day && rhs->getDueDate() == m_day) {
if (lhs->getProfitPerCycle() > rhs->getProfitPerCycle())
return false;
return true;
}
if (lhs->getDueDate() == m_day && rhs->getDueDate() != m_day)
return false;
if (rhs->getDueDate() == m_day)
return true;
if (lhs->getProfitPerCycle() > rhs->getProfitPerCycle())
return false;
return true;
}
Order.h
/*
* Order.h
*
* Created on: Oct 11, 2017
*/
#ifndef ORDER_H_
#define ORDER_H_
#include “Product.h”
class Order {
public:
Order(int, int, int, int, int);
int getOrderID() const;
const Product* const getProduct() const;
int getQuantity() const;
int getDueDate() const;
int getUnitProfit() const;
int getTotalCycles() const;
int getMade(int p_day = 4) const;
int getDayMade(int) const;
int getQuantityLeft() const;
int getProfitPerCycle() const;
int calculateProfit() const;
void setDayMade(int, int);
private:
int m_orderid, m_quantity, m_duedate, m_unitprofit;
Product m_product;
int m_daymade[5];
};
class OrderCompare {
public:
OrderCompare(const int& p_day = 0);
bool operator()(const Order* lhs, const Order* rhs) const;
private:
int m_day;
};
#endif /* ORDER_H_ */
Product.cpp
/*
* Product.cpp
*
* Created on: Oct 11, 2017
*/
#include “Product.h”
#include “Component.h”
const int cycleMap[] = { 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7 };
const int compMap[16][4] = { { 0, 4, 6, 8 }, { 0, 4, 6, 9 }, { 0, 4, 7, 8 }, {
0, 4, 7, 9 }, { 1, 4, 6, 8 }, { 1, 4, 6, 9 }, { 1, 4, 7, 8 }, { 1, 4, 7,
9 }, { 2, 5, 6, 8 }, { 2, 5, 6, 9 }, { 2, 5, 7, 8 }, { 2, 5, 7, 9 }, {
3, 5, 6, 8 }, { 3, 5, 6, 9 }, { 3, 5, 7, 8 }, { 3, 5, 7, 9 } };
Product::Product(int p_id) :
Item(p_id), m_cycles(cycleMap[p_id]) {
for (int i = 0; i < 4; i++) {
m_comps[i] = new Component(compMap[p_id][i]);
m_cost += m_comps[i]->getCost();
}
m_cost += (m_cycles * 100);
}
Product::~Product() {
for (int i = 0; i < 4; i++)
delete m_comps[i];
}
int Product::getCycles() const {
return m_cycles;
}
Component* Product::getComponent(int p_compnum) const {
return m_comps[p_compnum];
}
Product.h
/*
* Product.h
*
* Created on: Oct 11, 2017
*/
#ifndef PRODUCT_H_
#define PRODUCT_H_
#include “Item.h”
#include “Component.h”
extern const int costMap[10];
extern const char* nameMap[10];
class Product: public Item {
public:
Product(int);
~Product();
int getCycles() const;
Component* getComponent(int) const;
private:
int m_cycles;
Component* m_comps[4];
};
#endif /* PRODUCT_H_ */
Schedule.cpp
/*
* Schedule.cpp
*
* Created on: Oct 11, 2017
*/
#include
#include
#include
#include
#include “Schedule.h”
#include “Order.h”
Schedule::Schedule(streambuf* p_buffer) :
m_is(p_buffer), m_cycleDay { }, m_productionPlan { }, m_componentDemand { } {
for (string l; getline(m_is, l);) {
smatch m;
if (regex_match(l, m,
regex(
“\\[(\\d+),([0-9]|1[0-5]),([1-9]|1[0-9]|20),([0-4]),(\\d+)\\]”))) {
Order* order = new Order(stoi(m.str(1)), stoi(m.str(2)),
stoi(m.str(3)), stoi(m.str(4)), stoi(m.str(5)));
m_orders[stoi(m.str(1))] = order;
m_orderqueue.push(order);
} else
cout << “\nIncorrect format: ” << l << ” skipping…”;
}
}
void Schedule::process() {
for (int i = 0; i < 5; i++) {
int cycles = 0;
while (true) {
if (m_orderqueue.empty())
break;
Order* order = m_orderqueue.top();
if ((cycles + order->getTotalCycles()) > 2000) {
int cyclesleft = (2000 – cycles);
int quantity = int(
cyclesleft / order->getProduct()->getCycles());
if (quantity <= 0)
break;
m_productionPlan[order->getProduct()->getId()][i] += quantity;
for (int j = 0; j < 4; j++)
m_componentDemand[order->getProduct()->getComponent(j)->getId()][i] +=
1 * quantity;
cycles += (quantity * order->getProduct()->getCycles());
order->setDayMade(i, quantity);
m_orderqueue.pop();
m_orderqueue.push(order);
break;
} else {
m_productionPlan[order->getProduct()->getId()][i] +=
order->getQuantityLeft();
for (int j = 0; j < 4; j++)
m_componentDemand[order->getProduct()->getComponent(j)->getId()][i] +=
1 * order->getQuantityLeft();
cycles += order->getTotalCycles();
order->setDayMade(i, order->getQuantityLeft());
m_orderqueue.pop();
}
};
m_cycleDay[i] = cycles;
update(i + 1);
}
}
void Schedule::update(int p_day) {
m_orderqueue_type tempqueue = m_orderqueue_type(OrderCompare(p_day));
while (!m_orderqueue.empty()) {
tempqueue.push(m_orderqueue.top());
m_orderqueue.pop();
}
m_orderqueue = tempqueue;
}
void Schedule::print() {
writeProductionPlan(cout);
writeComponentDemand(cout);
writeSchedule(cout);
}
void Schedule::save(const char* p_fname) {
ofstream ofile(p_fname);
writeProductionPlan(ofile);
writeComponentDemand(ofile);
writeSchedule(ofile);
ofile.close();
}
void Schedule::writeHeader(ostream& out, const char* p_title,
const char* p_headers[], int p_size) {
out << endl << p_title << endl;
for (int i = 0; i < p_size; i++)
out << setw(10) << p_headers[i];
}
void Schedule::writeProductionPlan(ostream& out) {
const char* ProductionPlanHeader[] = { “pcId”, “Day0”, “Day1”, “Day2”,
“Day3”, “Day4”, “Total” };
writeHeader(out, “Production plan”, ProductionPlanHeader, 7);
for (int i = 0; i < 15; i++) {
int sum = 0;
out << endl << setw(10) << i;
for (int j = 0; j < 5; j++) {
sum += m_productionPlan[i][j];
out << setw(10) << m_productionPlan[i][j];
}
out << setw(10) << sum;
}
out << endl << endl << “Production Cycles” << endl;
for (int i = 1; i < 6; i++)
out << setw(10) << ProductionPlanHeader[i];
out << endl;
for (int i = 0; i < 5; i++)
out << setw(10) << m_cycleDay[i];
cout << endl;
}
void Schedule::writeComponentDemand(ostream& out) {
const char* ComponentDemandHeader[] = { “compId”, “Day0”, “Day1”, “Day2”,
“Day3”, “Day4”, “Total” };
writeHeader(out, “Component demand”, ComponentDemandHeader, 7);
for (int i = 0; i < 10; i++) {
int sum = 0;
out << endl << setw(10) << i;
for (int j = 0; j < 5; j++) {
sum += m_componentDemand[i][j];
out << setw(10) << m_componentDemand[i][j];
}
out << setw(10) << sum;
}
cout << endl;
}
void Schedule::writeOrder(ostream& out, Order* const & p_order) {
out << endl << setw(10) << p_order->getOrderID() << setw(10)
<< p_order->getProduct()->getId() << setw(10)
<< p_order->getQuantity() << setw(10) << p_order->getDueDate()
<< setw(10) << p_order->getUnitProfit() << setw(10);
for (int i = 0; i < 5; i++)
out << p_order->getDayMade(i) << setw(10);
out << p_order->calculateProfit() << setw(10);
}
void Schedule::writeSchedule(ostream& out) {
int totalprofit = 0;
const char* ScheduleHeader[] = { “orderId”, “pcId”, “qty”, “dueDate”,
“profit”, “Day0”, “Day1”, “Day2”, “Day3”, “Day4”, “TtlProfit” };
writeHeader(out, “Satisfied Orders”, ScheduleHeader, 11);
for (auto it = m_orders.cbegin(); it != m_orders.cend();) {
if (it->second->getMade(it->second->getDueDate())
!= it->second->getQuantity())
++it;
else {
totalprofit += it->second->calculateProfit();
writeOrder(out, it->second);
delete it->second;
it = m_orders.erase(it);
}
}
writeHeader(out, “Unsatisfied Orders”, ScheduleHeader, 11);
for (auto it = m_orders.cbegin(); it != m_orders.cend();) {
if (it->second->getMade() == 0)
++it;
else {
totalprofit += it->second->calculateProfit();
writeOrder(out, it->second);
delete it->second;
it = m_orders.erase(it);
}
}
writeHeader(out, “Canceled Orders”, ScheduleHeader, 11);
for (auto it = m_orders.cbegin(); it != m_orders.cend();) {
totalprofit += it->second->calculateProfit();
writeOrder(out, it->second);
delete it->second;
it = m_orders.erase(it);
}
cout << endl << “Total Profit: ” << totalprofit;
cout << endl;
}
Schedule.h
/*
* Schedule.h
*
* Created on: Oct 11, 2017
*/
#ifndef SCHEDULE_H_
#define SCHEDULE_H_
#include
#include
#include
#include “Order.h”
using namespace std;
class Schedule {
public:
Schedule(streambuf*);
void process();
void print();
void save(const char*);
private:
istream m_is;
int m_cycleDay[5];
int m_productionPlan[15][5];
int m_componentDemand[10][5];
map m_orders;
typedef priority_queue, OrderCompare> m_orderqueue_type;
m_orderqueue_type m_orderqueue;
void update(int);
void writeHeader(ostream&, const char*, const char*[], int);
void writeProductionPlan(ostream&);
void writeComponentDemand(ostream&);
void writeOrder(ostream&, Order* const &);
void writeSchedule(ostream&);
};
#endif /* SCHEDULE_H_ */