Scheduling N jobs on a Single machine with multiple objectives and set-up times

Abstract EN

In this paper we consider the problem of scheduling n jobs on a single machine, where the jobs are divided into F families, each family f, (f = 1, …, F) contains jobs.

Our aim in this study is to find the optimal and near optimal schedule for the n jobs to minimize total weighted completion time and weighted number of tardy jobs.

For solving this problem we propose a new lower bound (LB) based on relaxation of set-up times and decomposes the problem into tow sub-problems.

To be used in a branch and bound algorithm which used to find the optimal solution.

We also applied some local search methods to find near optimal solution such as (algorithm AH, Threshold Accepting, Tabu search (TS)).