The Permutation Flow-Shop Problem

Problem Description

This problem is described in Exercise 7.6.4 in .

Program Descriptions

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

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

[ pi , 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: pi - 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 .

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

[ pi , 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: pi - 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.

Bibliography

1. D. P. Kroese and R. Y. Rubinstein.
The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning.
Springer, 2004.