Solving the Single Machine Problem with Quadratic Earliness and Tardiness Penalties

Nowadays, scheduling problems have a considerable application in production and service systems. In this paper, we consider the scheduling of n jobs on a single machine assuming no machine idleness, non-preemptive jobs and equal process times. In many of previous researches, because of the delivery dalays and holding costs, earliness and tardiness penalties emerge in the form of linear combinations in objective functions. However, minimizing the weighted quadratic earliness and tardiness penalties is considered in this paper. A branch and bound algorithm including some dominance rules, lower bounds and upper bounds is proposed to solve the problem. Finally, the efficiency of proposed method is proved via some test problems.