The Permutation Flow-Shop Problem

Problem Description

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

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 [1].

    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.