CPSC 433: Search example

	Rob Kremer
	Search Samples: Paint Shop CPSC 433: Artificial Intelligence	Computer Science

Problem Description:

This is a simplified version of a problem I worked on in the real world.

There is a supply of cars waiting to be painted, n paint bays, and orders from various customers. Let's say there is an infinite supply of cars to keep the problem simple. The orders specify 1 or more cars, and what color to paint each of them, and specify a delivery time. Orders cannot be split, so an order is only filled when all the cars on it have been painted the correct color. Some customers are important customers and others are just normal customers.

The paint shop operates for 8h/day. It takes 1h to paint a car. Only one car can be in any one paint bay at a time. A paint bay can keep going continuously without a break with the same color, but it takes 3h to change the color of the paint bay and in that 3h, the paint bay is not available.

Your job is to (1) schedule cars in paint bays, (2) schedule paint-color changes for paint bays, and (3) assign painted cars to orders as they come out of the paint bays such that you fill as many orders as you can on time. Your schedule will be judged according to the following utility function:

rule number	penalty	antecedent
1	*nCarsInOrder/2 daysLate**	for each late order for a normal customer
2	*2 nCarsInOrder/2 * daysLate**	for each late order for an important customer

Give a fully-specified formal model and process for an arbitrary paint shop problem which specifies:

the number of paint bays and the initial color of each
a set of orders, each specifying an order number, a delivery date, whether the customer is important or not, and a list of colors with the number of cars required for each color

Also give a fully-specified formal search instance for the following problem:

3 paint bays: red, red, yellow
Orders:

order number	delivery date (days from now)	important	color	n cars
1	2	yes	red	20
			green	2
			orange	4
2	1	no	red	10
			yellow	1
			green	5
3	2	yes	green	6

CPSC 433: Artificial Intelligence

Last updated 2013-08-31 00:00

Rob Kremer