
## Improving Local Search For Fuzzy Scheduling Problems

M J Geiger , S Petrovic Automated Scheduling, Optimisation & Planning Group, School of Computer Science & IT, University of Nottingham Key words to describe the work: Fuzzy scheduling, dynamic scheduling, multi criteria optimization, local search. 

Key Results: In the investigated problem, multi criteria local search strategies may outperform their single criterion counterparts. 

How does the work advance the state-of-the-art?: The proposed technique successfully improves current local search heuristics for fuzzy scheduling problems that bear fitness plateaus in the search space. Motivation (problems addressed): Although there do exist various approaches for real-world scheduling problems, the methodology is not yet fully investigated and understood. In particular the field of fuzzy scheduling is a new aspect of optimization in real-world problems. 

## Introduction

The integration of fuzzy set theory and fuzzy logic into scheduling is a rather new aspect with growing importance for manufacturing applications [1, 4], resulting in various unsolved aspects. 

In the current paper, we investigate an improved local search technique for fuzzy scheduling problems with fitness plateaus, using a multi criteria formulation of the problem. We especially address the problem of changing job priorities over time as studied at the Sherwood Press Ltd, a Nottingham based printing company, who is a collaborator on the project. 

## A Fuzzy Scheduling Problem In The Printing Industry

In the studied problem, a set of machines 
{ ,..., } M = M1 Mm exists performing operations on a set of jobs { ,..., } 1 n J = J J . Each job i J can be described as an ordered set of tasks { ,..., } Ti = Ti1 Tit whereas each task may be processed on a specific machine with a nonnegative processing time pij . 

The relative importance of the jobs is modelled by introducing weights wi for each job i J which may change over time. As studied at Sherwood Press Ltd, due dates may exist as so called 'promised delivery dates', based upon an individual agreement with each customer. 

Here, the products are supposed to be shipped within a time interval and not necessarily on a specific day. 

Accordingly, the notion of tardiness of a job i J can properly be addresses using a fuzzy due date definition Di
~ , consisting of a doublet 1 2 (, ) i i d d with monotonically decreasing satisfaction degree and a correspondingly increasing fuzzy tardiness Ti
~ as shown in fig. 1. 

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

In addition a tardiness penalty ' Ti has been introduced, allowing penalty values > 1, as described in fig. 2. 

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

Two overall objective definitions have been studied. First, the single-criterion minimization of the total weighted tardiness =∑wi Ti c x ~ ( ) 1 , and second the bicriteria extension as a vector optimization problem min( , ) 1 2 c c with 2 () ' i i *c x wT* =∑ , leading to the problem of identifying all Pareto optimal solutions [2]. 

The introduction of the tardiness penalty as described in fig. 2 is motivated by the existence of fitness plateaus in the search space with respect to 