Operations Resarch Optimal Scheduling

Question

Consider the following problem:

A car manufacturing company needs to transport car frames, which are $10$ cubic units each, and wheels, which are $2$ cubic units each, across the Atlantic ocean. They use boats which have 50 cubic units of storage space to transport the frames, and planes which have $20$ cubic units of storage space to transport the tires. Each car needs $4$ wheels, so if $x$ is the number of cars to transport then $4x$ is the number of wheels.

The company wants to minimize the total wasted space when they ship. For example, if they choose to transport $16$ cars ($160$ cubic units) and $16\cdot4=64$ wheels ($128$ cubic units), then they will need $4$ boats and $7$ planes, and will have $40+12= 52$ units of wasted space.

I'm interested in algorithms for solving this type of problem, given a desired range of solutions, i.e. $10< x < 15$. The obvious answer is to use the LCM to find a perfect solution, but what if there is no perfect solution within the range?

Any thoughts or research papers on this topic would be very helpful!

Thanks

Answer 1

Let $X=$ number of cars to build, $S=$ the number of ships to use, and $P=$ the number of planes to use. Let $L,U$ be the lower and upper production range for $X$.

We want to minimize the objective function: $Z(S,P,X)=50S+20P-12X$

Subject to constraints:

• $50S-10X \geq 0$
• $20P-8X\geq0$
• $L\leq X \leq U$
• $P,S\geq 0$
• $X,P,S \in \mathbb{N}$

An this is a linear integer program. You can tackle it using the Branch and Bound algorithm, as implemented in any integer programming package.