\documentstyle[12pt,fullpage]{article}
\begin{document}
\begin{center}
{\Large \bf C\&O 370} \\
{\Large \bf HOMEWORK \#4}
\end{center}
\medskip
Due: Monday, November 20

\medskip
\noindent
{\bf Reading} \\
\begin{tabular}{lll}
~~~Chapter 9 & (pp. 366-385) & Integer Programming:  Models \& Modelling\\
~~~Chapter 9 & (pp. 402-407) & Solution Methods:  Cutting Planes\\
$\ast$ Chapter 9 & (pp. 385-402) & Solution Methods:  Branch \&
Bound/Enumeration\\
~~~Chvatal & (pp. 195-211) & Large-Scale L.P.'s:  Column Generation Technique
\end{tabular}
\begin{flushleft}
$\ast$ Optional reading - you may need it for your projects.
\end{flushleft}

\begin{enumerate}
\item[4.1]
[30]\\
A printer has six jobs, $(J_{1}, J_{2}, \ldots , J_{6})$, to be run on a
single printing press.
The run-sequence of jobs must obey the following precedence restrictions:

\vspace{2.50in}
Thus, for example, $J_{5}$ may not start before both of $J_{2}$ and $J_{4}$
have been completed.

The following table gives the required run time (hrs.) and due date
(cumulative hours from time 0) of
each job:

\begin{center}
\begin{tabular}{l|cccccc}
 & $J_{1}$ & $J_{2}$ & $J_{3}$ & $J_{4}$ & $J_{5}$ & $J_{6}$ \\ \hline
Run Time & 2 & 3 & 4 & 3 & 2 & 1\\
Due Date & 3 & 6 & 9 & 7 & 11 & 7
\end{tabular}
\end{center}
\begin{itemize}
\item[(a)]
Develop a model for determining a job run-sequence that satisfies the
precedence restrictions and
minimizes the maximum lateness of any job.
\item[(b)]
Solve your model of part (a) by a method of your choice.
\end{itemize}

\item[4.2]
[20]\\
Use the column generation technique to solve (approximately) the cutting
stock problem for which
15-ft. boards are to be cut to satisfy the following demands: 10 3-ft.
boards, 20 5-ft. boards,
15 8-ft. boards and 8 2-ft. boards.
\end{enumerate}

\vspace{.50in}
\noindent
{\bf Problems}

\begin{flushleft}
{\bf Case Study \#3} [50]
\end{flushleft}

A publisher wishes to contract a set of five manuscripts to a set of three
print shops for
typesetting.
The table below gives the cost (upper triangle) and time required (lower
triangle) for each
printshop to do each manuscript.
Printshops 1, 2 and 3 have, respectively, only 4, 7, and 5 weeks available
to work for the publisher.
No printshop may get a partial manuscript, and manuscripts 1 and 2 must go
to the same printshop.

Each shop will discount its cost by 20\% on each manuscript it gets in
excess of (the most costly) one.
There is a fixed cost of \$100 charged by each shop for contract
preparation but is levied only
by shops which are given at least one manuscript.

\begin{center}
{\bf MANUSCRIPTS}
\end{center}
\begin{center}
\begin{tabular}{c|c|c|c|c|c|}
  & $~~~$1$~~~$ & $~~~$2$~~~$ & $~~~$3$~~~$ & $~~~$4$~~~$ & $~~~$5$~~~$ \\
\hline \\
$~~~$1$~~~$ & & & & & \\
\hline \\
2 & & & & & \\
\hline \\
3 & & & & & \\ \hline
\end{tabular}
\end{center}
\begin{center}
{\bf COST (\$ X 100) / TIME (WKS) DATA}
\end{center}
Determine how the publisher should distribute the five manuscripts amongst the
three print shops in order to minimize the total cost of getting all of
them typeset.

\end{document}






