Models Knapsack Line Path Sequencing TSP General Options
 > Teach Dynamic Programming Add-in -Sequencing
 Many operational problems in manufacturing, service and distribution require the sequencing of various types of activities or items. Examples include a production facility in which chassis must be sequenced through an assembly line, an express mail service where parcels and letters must be routed for delivery, and a utility company that must schedule repair work. In this section, we introduce a robust dynamic programming formulation that can be used to tackle a number of such problems. In most cases, however, the size of the state space is an exponential function of the number of items being sequenced. To choose a sequencing problem select the Sequencing option button on the Problem Definition dialog. Choose a name for the model and specify whether to maximize or minimize the objective. Specify the number of items to be sequenced. We discuss the data form option after the model is described below.

As a prototype, consider the problem of sequencing a set of n jobs through a single machine that can work on only one job at a time. Once a job is started, it must be completed without preemption. The time required to process job j once the machine begins to work on it is p(j) for j = 1,...,n. The associated cost c(j,t) is a function of its completion time t and can take a variety of forms, the simplest being

c(j,t) = a(j)t

where a(j) is the cost per unit time for job j. This form admits a very simple solution when the objective is to minimize the total completion cost of all the jobs. The optimum is obtained by computing the ratio p(j)/a(j) for each job and then sequencing them in order of increasing values of this ratio. The job with the smallest ratio is processed first, the job with next smallest ratio is processed second, and so on until all jobs are completed. Ties may be broken arbitrarily.

A much more difficult problem results when each job j has a due date b(j). The cost of a job is zero if it is completed before its due date but increases linearly if it is tardy. In our models, a(j) is referred to as the penalty for a late job.

The goal of the optimization is to determine the sequence that has the smallest total cost. The table gives the relevant parameters for a 4-job instance.

There are 4! = 24 possible solutions. For the solution (3, 1, 2, 4), the completion times are 7, 12, 21 and 31 respectively. Jobs 3 and 1 are completed before their due date so no cost is incurred. Job 2 is 11 days late resulting in a cost of \$440 and job 4 is 14 days late resulting in a cost of \$420. The total cost is therefore \$860.

Returning to the Problem Definition Dialog

The problem definition dialog at the top of this page has various options for specifying data forms for the sequencing problem. When the Make Random Problem box is checked, the random selects data to create interesting problems. The DP model of the sequencing problem is robust regarding the model for the objective function. We try to illustrate this with the various data forms provided.

The data in the table for the example shows columns for time, due date and penalty. The amount of data included in the table depends on the Data Form entry on the problem definition dialog. The table above is data form 1. It assumes that the job penalty is constant with the number of days late. If we had chosen data form 0, the penalty column is not included. The jobs are assumed to have equal late penalties of 1. With data form 2, a matrix is constructed to show the late penalty as a function of the number of days late. This would be useful when the late penalties are nonlinear with time. The number of columns in this matrix is equal to the total of the job times assigned during the generation process. For the example that number is in cell Q15, so a table with 31 columns would be constructed for data form 2. If the number of columns is more than those available on the worksheet, you will receive an error message.

The initial worksheet constructed depends on whether the Make Random Problem box is checked on the dialog. The Max Time entry provides an upper bound to the job times when the Make Random Problem is checked. With the default value of 10, all job times are less than or equal to 10 as in the example. Using other maximum time entries results in problems with greater time variety. With the random option, due dates are are randomly selected using the total job times as an upper bound. That sum is calculated immediately below the time column. Even when the Make Random Problem box is not checked, the jobs are assigned random due times. Any numbers placed on the data table by the add-in generation process can be replaced by the user.

When the Sequence Restrictions box is checked, a table is included on the worksheet to restrict the order of the sequence. The table below shows a problem with eight jobs. The 1 in cell (1,2) requires that job 2 precede job 1 in the sequence. Restrictions such as these are easy to incorporate in the DP algorithm and actually make the problem simpler.

DP Model

 The add-in automatically creates the model that solves the DP for a given number of jobs. You can see the model by creating an example with the TeachDP add-in or by looking at the example workbook for this section (Worksheet Seq4 in teachdpdem.xls). The figure at the left shows the state and decision vectors for the model example. The model requires a state variable for each position in the sequence. The state defines the set of jobs that are already scheduled. There is a single decision variable that is the index of the next job to schedule.

Solving the Problem

Clicking the Solve button solves the problem. The solution statistics are below. The program first generates the states. Since there are four binary state variables, there are 16 states in the exhaustively generated set.

The figure below shows the decision network for the example. Each node represents a state. Each arc represents a decision that leads from one state to another. Since a state indicates the set of completed jobs, the finish time of the set can computed as the sum of the job times for the jobs in the set. Given the state, the cost of adding a job to the set can be computed and assigned to the decision arc. The DP solver has the problem of finding the shortest path through the decision network from some initial state to a final state. The heavy lines in the figure show the arcs and nodes on the optimum path. The path starts at the initial state (0,0,0,0) and ends at the final state (1,1,1,1).

The DP solution algorithm works backwards starting from (1,1,1,1). It firsts finds the optimum decision from each of the states with three 1's. These decisions are trivial. For example, there is only one way to go from (1,1,1,0), and that is J4. The cost of J4 leading from (1,1,1,0) to (1,1,1,1) is 420. We assign that value to state (1,1,1,0). Retreating to the states with two 1 entries, there are two possible decisions. The optimization finds the one that yields the smallest value. For example, from state (1,0,1,0), J2 and J4 are the decisions. Given the data the optimum is J2 with a cost of 440. It leads to (1,1,1,0). Continuing with the states with only one entry with value 1, each state has three decisions. All must be evaluated to find the optimum at each state. For the example, we find that from state (0,0,1,0) the optimum is J1. The cost associated with that decision is 0 because J1 is completed on time. There are four feasible decisions leading from (0,0,0,0). The optimum is J3 leading to state (0,0,1,0).

At the completion of the solution process, we have for each state the optimum decision and the optimum cost to reach the final state. One last process is required.

Recovering the Optimum

After the DP process is complete, we can find the optimum from any state to the final state. Since we have only one initial state, (0,0,0,0), we will find the path from (0,0,0,0) to (1,1,1,1). The process is called recovering the optimum.

State (0,0,0,0) has the optimum decision J3. The value associated with (0,0,0,0) is 860, the length of the path to (1,1,1,1). We record this as the first row of our solution matrix. The decision leads to state (0,0,1,0), where the optimum decision is J1 with cost of 860. It is the same as (0,0,0,0) since the cost of J3 is 0. This leads to state (1,0,1,0) where the value is again 860. Decision J2 with a cost of 440 then leads to (1,1,1,0). The value at this state is 420, the cost of the last decision J4. The last state has no more decisions, so this is the final state. The optimum sequence starting from the initial state is: J3, J1, J2 and J4 with a total cost of 860.

The Options command under the Teach DP menu allows various output alternatives to view the details of the DP process.

Summary

Although DP is quite efficient for small problems, the number of states grows exponentially with the number of jobs. This 4 job example has 16 states, a five job problem has 32 states, and in general the number of states is 2 raised to the power of the number of jobs.

Operations Research Models and Methods
Internet
by Paul A. Jensen