The Permutation Flow-Shop

Problem Description

In the permutation flow shop sequencing problem n jobs have to be processed (in the same order) on m machines. The objective is to find the permutation of jobs that will minimize the makespan, that is, the time at which the last job is completed on machine m. Let t(i,j) be the processing time (cost) for job i on machine j and let x = (x(1),x(2),...,x(n)) be a job permutation. Then the completion time C(x(i),j) for job i on machine j can be calculated as follows:

     C(x1,1)  =  t(x(1),1)
     C(xi,1)  =  C(x(i-1),1) + t(x(i),1),  i  =  2,...,n 
     C(x1,j)  =  C(x(1),j-1) + t(x(1),j),  j  =  2,...,m 
     C(xi,j)  =  max{C(x(i-1),j),C(x(i),j-1)} + t(x(i),j), 
                 for all i  =  2,...,n,  j  =  2,...,m

The objective is to minimize S(x) = C(x(n),m). The trajectory generation for the PFSP is exactly the same as in the TSP.

This problem is described in Exercise 7.6.4 in [7].

Programs

pfsp.m
This MATLAB program gives the best found permutation via the CE method.

Usage:
Call the program from MATLAB, with the following syntax:

[x,t]=pfsp(N,rho,alpha,traj,n,m,t,z)

Example: [perm,cost]=pfsp(100,0.1,0.8,2,10,2,t,10)
where t is a 10 x 2 matrix of costs.

Inputs:
N	-	Number of samples to generate each round
rho	-	fraction of best samples to take
alpha	-	smoothing parameter
traj	-	0, node transitions, x(1)=1
		1, node transitions, x(1) random
		2, node placement (default)
n	-	number of jobs
m	-	number of machines
t	-	t(i,j) is the cost of job i on machine j
z	-	number of succesive rho-th quantiles the same before stop
Outputs:
x	-	the output permutation
t	-	the cost (in time) matrix used

gpfsp.m This program is used internally to generate tours via node transitions.

gpfsp2.m This program is used internally to generate tours via node placement, using the first row of the P matrix to generate the first position.

gpfsp3.m This program is used internally to generate tours via node placement, using a random row of the P matrix to generate the first position.

fpfsp.m
This MATLAB program gives the best found permutation via the CE method, using ``fast'' trajectory generation, as mentioned in Remark 4.12, and described in Algorithms 4.11.3 and 4.11.4, as well as Section 4.11.2 in [7].

Usage:
Call the program from MATLAB, with the following syntax:

[x,t]=fpfsp(N,rho,alpha,traj,n,m,t,z)

Example: [perm,cost]=fpfsp(200,0.05,0.75,3,12,1,t,10)
where t is a 12 x 3 matrix of costs.

Inputs:
N	-	Number of samples to generate each round
rho	-	fraction of best samples to take
alpha	-	smoothing parameter
traj	-	0, alias technique (default) uses x% = 70%
		1, composition method
n	-	number of jobs
m	-	number of machines
t	-	t(i,j) is the cost of job i on machine j
z	-	number of succesive rho-th quantiles the same before stop
Outputs:
x	-	the output permutation
t	-	the cost (in time) matrix used

fgpfsp.m This program is used internally to generate tours via the alias speed-up.

fgpfsp2.m This program is used internally to generate tours via the composition speed-up.

spfsp.m This program is used internally to evaluate the performance of these algorithms.