We consider a two-machine scheduling problem in an openshop with blocking. We are given the processing times of n jobs on both machines, and the objective is to minimize the makespan. Symbolically, we are dealing with the problem O2|block|Cmax. Four approaches are proposed: (1) A flowshop-based heuristic that is based on the Gilmore-Gomory algorithm for the F2|block|Cmax problem; (2) Two heuristics based on the idea of ‘matching’ to minimize ‘potential’ idle time on either machine, and (3) A random search algorithm that emulates some important characteristics of other ‘soflcomputing’ meta-heuristics. We derive some lower and upper bounds on the optimal objective value that should assist the decision maker in evaluating the result of a particular application. Numerical experiments with the procedures compare their performance under varying conditions and demonstrate the efficacy of the random search algorithm.
|Number of pages||11|
|Journal||Journal of the Chinese Institute of Industrial Engineers|
|State||Published - 1 Jan 2000|