Production Planning & Scheduling. Optimization modeling exercises

Objectives:

• Problem identification and optimization model formulation
• Solving methods: use of mathematical programming to formulate the planning models

Exercise 1¹

A large company wishes to move some of its departments out of London. There are benefits to be derived from doing this (cheaper housing, government incentives, easier recruitment, etc.), which have been costed. Also, however, there will be greater costs of communication between departments. These have also been costed for all possible locations of each department.

The company comprises five departments (A, B, C, D and E). The possible cities for relocation are Bristol and Brighton, or a department may be kept in London. None of these cities (including London) may be the location for more than three of the departments. Benefits to be derived from each relocation are given (in thousands of pounds per year) as follows:

Communication costs are of the form C_ikD_jl, where C_ik is the quantity of communication between departments i and k per year and D_jl is the cost per unit of communication between cities j and l. C_ik and D_jl are given by the following tables:

Quantities of communication C_ik (in thousands of units)

Costs per unit of communication D_jl (in £)

Q: Where should each department be located so as to minimize overall yearly cost?

You should build the optimization model to answer this question

¹ This exercise has been extracted from H. Paul Williams. Model Building in Mathematical Programming. Wiley.

Exercise 2

A plant manager needs help to schedule production and inventories for multiple products over time when facing limited resources such as labor, materials (gold), and machine capacities in each period (a four months period is considered). Two types of products are manufactured (bands and coils) from the raw material (gold). The following table gives the demand for the defined planning horizon:

Backorders are allowed, so the optimization model should handle goals such as reducing the backlogs at the end and reaching the target inventory levels. Bill of materials (BoM) is described in the following table (the resource requirements are per production unit):

The availability of resources for the given planning horizon is given by:

The unit cost of production, inventory, and backlogging can change over time during the planning horizon. The following tables show these parameters:

Bounds on the ending backorder levels can be enforced (in the problem instance are set to 1000 ton/month each product). Additionally, a target ending inventory level can be specified too (200 tons each product).

Q: The objective is to minimize the total cost of production, inventory, and backlogging.

Exercise 3

A computer assembly company has to determine the processing order of a set of custom computers on an assembly flow-shop. The company uses various components of different types. For instance: different CPU’s, disk drives or video cards. The company builds several computer models consisting on various configurations of assembled components of different types. They following components are available:

• CPU’s: “173GHz”, “153GHz” and “152GHz”
• Storage disks: “SDD512Mb”, “HDD1Tb” and “HDD512Mb”
• Video cards: “NVIDIA” and “AMDRadeon”
• Optical devices: “CDRW” and “DVDRW”
• Communication devices: “Ethernet” and “Bluetooth”

Depending on the combination of components, the company builds six different computer models: from Model A to F. To build a given computer model, a sequence of activities must be performed among the following ones:

• Install CPU,
• Install Disk,
• Install Optical Device,
• Install GPU (video card),
• Install Ethernet,
• Install Bluetooth,
• Test,
• Pack

The following resource types are available for these activities:

• CPU Installer,
• Drive Installer (hard and optical disks),
• Card Installer,
• Communications Installer (Ethernet and Bluetooth),
• Tester,
• Packer

For each type, there is one single resource. An activity type is characterized by the following attributes:

• Activity label (name)
• Activity duration;
• Required resource type
• A list of precedent activities

The fabrication of each computer model type is then specified by a list of activities according to the structure described above.

For example, assembling computer Model A consist of the following activities:

The fabrication of the other computer model types is specified in a similar way. The data file provided with this statement defines all the required data for solving the problem, including the quantities to be produced of each computer model type.

Therefore, a particular activity has to be defined for each computer to be manufactured. These individual activities can be represented according to the following structure:

• a defined activity type,
• for each computer type,
• for each computer to be manufactured

For instance, if Model A involves 7 activity types and 5 computers of Model A have to be manufactured, that means the production of computers Model A involve 35 individual activities (e.g. 5 CPU installations, 5 disk installations, and so on). At this point, you should take into account that symmetric solutions have to be avoided.

The optimization objective is the minimization of the make-span defined as:

Q: Define a constraint programming model able to schedule all the required activities according to the declared objective. You have to use the interval and sequence decision variable types and the proper related constraints in order to ensure that:

• You eliminate all the possible symmetries in your model solution
• There is no overlapping in the use of each resource
• All the precedence rules declared by the input data are met.