Bu çalışmada, tek makineli bir sistemde hız değiştirme faaliyeti (HDF) ile birlikte işlerin çizelgelenmesi üzerinde durulmaktadır. Bir HDF, makinenin üretim hızının orijinal durumuna getirilmesi için uygulanan bir bakım faaliyeti olarak tanımlanmaktadır. Bu açıdan bakıldığında, bir işin HDF’den önce veya sonra planlanması sonucunda, işlerin işlem zamanları farklı değerler almaktadır. Ele alınan problem, iş sırası ve bu iş sırası içindeki HDF konumunun belirlenmesidir. Çözüme yönelik olarak şebeke gösterimine dayalı, en kısa yol tabanlı bir yöntem oluşturulmuştur. Önerilen yöntemde, ilk aşamada En Kısa İşlem Zamanı algoritması ile elde edilmiş iş sıralamasına göre bir şebeke oluşturulmaktadır. Daha sonra ilgili şebeke üzerinde en kısa yolu veren HDF ataması doğrusal programlama kullanılarak aranmakta ve bulunan yolun değeri makine için toplam tamamlanma zamanını vermektedir. Bundan sonra yerel arama prosedürü uygulanarak, her adımda iş sıralamaları üzerinde swap operasyonu (ikili değişim) kullanılmakta ve elde edilen yeni çözümler üzerinde yapılan sürekli karşılaştırmalar sonucu son çözüm elde edilmektedir.