\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,latexsym}

\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\topmargin}{-1in}
\addtolength{\textwidth}{1in}
\setlength{\textheight}{9.3in}

\pagestyle{plain}
\parindent 0pt
\pagenumbering{arabic}

%\input defs.tex

\begin{document}

\begin{center}

{\LARGE \bf The {\em Corrected } Wood Shop }\\
\bigskip
{\Large \bf CS 410 Summer 2000 }\\
{\Large \bf Homework Assignment 2 }\\
{\large \bf Due 11:30 AM, Tuesday July 11 }\\
\end{center}

\bigskip

{\large \bf Important note:}
This is only a portion of homework 2, not the complete assignment.

\bigskip

Wilson has set up shop in his garage.  Literally.  He has turned his
hobby of carpentry into an old-fashioned business he calls Wood Row,
which he runs out of his garage.  It was the logical place for it.  
It's not so easy to move a table saw, or much of the other equipment
he needs. \\

There are ten items he produces, which range from simple shelves to
elaborate desks.  
\footnote{The full list of items include beds, boxes, chairs, chests, desks,
doors, shelves, tables, toys, and trunks.}
Ever since he advertised with a ``Save the Rain Forest"
web site, he's been overloaded with job orders (go figure).  He hired
someone to help him, but since he has only one table saw, he's limited as
to how much he can produce.  He wrote out the dimensions of each piece of
wood needed for each item for Emily (his assistant) to use, each item
described on a separate page.   \\

He cut back his advertising to once a week, since in a week he can
usually complete all the orders he gets from a day's advertising.
Emily used to go through her book of directions from beginning to end,
cutting enough wood for the quantity of each item ordered (i.e., if 8
beds were ordered, she would cut wood for those before moving on to
cutting wood for the boxes ordered).  She had arranged her instruction
book alphabetically, so soon they noticed that the bed customers were
quite happy with the turn-around time, but the trunk customers were
threatening to bring their business elsewhere if they couldn't get their
trunks sooner, and the shelf customers just couldn't understand how a
simple shelf could take so long to produce. \\

So, Emily began researching scheduling theory.  She came in after
a weekend at the library, and told Wilson that if he would assign a
due date to each job, then she would optimize the order in which she cut
the wood.  If it were possible to have all jobs completed by their
due date, she would do that.  If such a schedule were not possible, then
she would essentially add a little to each due date until it was possible
to complete them all by their modified due date.  This had the effect of
minimizing how late the latest job would be (here {\it lateness} is measured
by how
much time after its due date a job is completed).  In scheduling theory, this
criteria is called {\bf minimum maximum lateness}, and an optimal algorithm 
for this criteria is called
the {\bf earliest due date rule (EDD)}, which simply schedules jobs in
order of their due dates (earliest due date first, etc.). \\

Customer relations improved dramatically.
Still, Wilson wondered about this algorithm.  Since shelves could be done
so quickly, he thought they ought to be able to produce some of those
early, thus quickly making some customers happy without significantly
impacting other customers.  Other problems surfaced
with how due dates were assigned, and after a month he asked Emily if
there weren't another algorithm they could try. \\

The next Monday Emily returned with a dramatically new plan.
Instead of due dates, they would assign priorities (weights) to each job.
The new criterion would be to minimize the weighted completion
time (sum the product of the weight and completion
time of each job).  This can be optimally accomplished by the
smallest ratio rule, which schedules the jobs in order of non-decreasing
("increasing") ratio of the amount of time required to process a job, 
divided by its weight.  Customer relations improved even more, and
Wilson was able to buy more equipment and a manufacturing building, and
Wood Row has since gone multinational.  Wilson is planning to retire so
he and his wife can have time to start a family.  Emily is currently the vice
president in charge of operations, and earning twice what her older
brother makes at his successful dot-com.  \\


\smallskip
{\bf Formally:} In this situation,
each job $j$ has 
\begin{itemize}
\item 
  a processing time $p_j$ (amount of time it will take) 
\item 
  a due ``date" $d_j$  (time units may be other than days)
\item 
  a weight or priority $w_j$
\end{itemize}

Only one job is run at a time, starting at time=0.  The time units may
be considered hours. \\
In a particular schedule (ordering of the jobs), $C_j$ indicates the 
completion time of job j. \\

The {\bf EDD} rule schedules jobs in order of nondecreasing $d_j$.
This rule can be proven to minimize the maximum $C_j - d_j$. \\

The {\bf ratio} rule schedules jobs in order of nondecreasing 
$p_j / w_j$.
This rule can be proven to minimize 
$\Sigma_j w_j C_j$,
the weighted completion time. 
\\

\medskip

\begin{center}
{\large \bf Analysis}
\end{center}
\smallskip

In addition to the programming assignment detailed separately, you need
to perform the following analysis:

\begin{description}
\item[Story analysis] Complete the sentence:  The moral of 
the story is \makebox[1.7in]{\hrulefill}

\item[Algorithm analysis] 
You can use any method to solve these (e.g. calculate 
by hand or by write some additional code).  You must show how you arrived 
at your solution.
\begin{enumerate}
\item
Using the $p_j$, $d_j$, and $w_j$ in the code you are given,
and given a week where exactly one of each item is ordered,
what is the minimum maximum lateness?  Which item(s) achieve this
maximum lateness?  
\item
Same setup as previous question.  How many items are always completed sooner
using than ratio rule than they were using the EDD rule?  What is the
maximum lateness (defined with $d_j$ used for EDD rule) when using the 
ratio rule?  How many jobs are completed by their due date under each
of the two rules?
\item
When will the EDD rule give us the same results as the ratio rule?
More specifically, when will the EDD rule give us an optimal solution for 
the weighted completion time criterion, while the ratio rule gives an 
optimal solution for the min max lateness rule?
For example, if all jobs are the same (same $p_j$, $d_j$, and $w_j$),
then all schedules are optimal.
Can you think of any other situation?  
What if we set {\bf $d_j = \max_i (w_i) - w_j$ }(so more weight gets translated
as an earlier due date)?  Are there any other modifications we can
effect?

\end{enumerate}
\end{description}


\end{document}
