1c , as there do exist numerous alternatives x with identical objective values 1c . 

## Investigation Of Local Search Strategies

Three basic local search neighbourhoods have been investigated within a hillclimbing framework [3]. 

- Forward shift (FSH), removing a job from a current schedule and reinserting it after a succeeding one. 

- Backward shift (BSH), removing a job from its position and reinserting it before a preceding job. 

- Exchange (EX), exchanging the position of two jobs. 

Each neighbourhood structure has been allowed to compute 20,000 alternatives while the weights wi have been altered after 5,000, 10,000 and 15,000 iterations in order to simulate dynamic changing job priorities. The tests have been performed on 50 problem instances generated based on the job characteristics of the practical case in the Sherwood Press, and the results have been averaged. 

## Results

Conducting significance tests at a level of 0.99, it has been possible to observe that for the single criterion formulation EX leads in 90% of the instances to better results than BSH, which is found to be better than FSH. The results are stable over time, thus the altering of the weights does not lead to significantly different results. The comparison of the neighbourhood search on the bicriteria extension of the problem with the results of the single criterion version reveals an interesting pattern, shown in fig. 3. After approximately 1,000 initial iterations, the single criterion search is able to significantly outperform the bicriteria formulation in more problem instances than vice versa. However, this effect is reversed after the local search approaches have been allowed more evaluations. 

While the monocriterion hillclimber tends to get stuck in local optima, its bicriterion counterpart successfully overcomes local optimality, leading to significantly better results. 

As fig. 3 reveals, this effect is each time repeated after changing the weight settings. While the neighbourhood search for the single criterion problem allows comparably fast improvements, its advantage over the multi criterion extension is decreasing over time, and the results are reversed given the necessary amount of iterations. 

![0_image_0.png](0_image_0.png)

## Conclusions

A fuzzy scheduling problem derived from a practical application in the printing industry has been presented. It is possible to show that for the studied problem, multi criteria local search strategies may outperform their single criterion counterparts at the cost of additional computations. 

## References

[1] Ishii, H. (2000) Scheduling problems with fuzzy constraints, in: R. Słowiński, M. Hapke, Scheduling Under Fuzziness (pp. 81-112), Heidelberg: Physica. 

[2] Knowles, J.D., Watson, R.A., & Corne, D.W. 

(2001) Reducing local optima in single-objective problems by multi-objectivization, in: E. Zitzler, K. Deb, L. Thiele & C.A. Coello Coello, Evolutionary Multi-Criterion Optimization: 
Proceedings of the First International Conference EMO 2001 (pp. 269-283), Berlin: Springer. 

[3] Reeves, C.R. (1999) Landscapes, operators and heuristic search. Annals of Operations Research, 86, 473-490. 

[4] Slany, W. (1996) Scheduling as a fuzzy multiple criteria optimization problem. Fuzzy Sets and Systems, 78, 197-222. 

## Acknowledgements

We would like to thank our collaborators at Sherwood Press Ltd, Nottingham, Mr Colin Edis, Mr James Timpson and Ms Jenny Bull. This research is supported by the British Engineering and Physical Sciences Research Council (EPSRC), UK (Grant No. GR/R95319/01). 