A tabu-search algorithm for scheduling jobs with controllable processing times on a single machine to meet due-dates

摘要

In many real-world production systems, it is important to schedule jobs such that they could be processed and shipped with no delay. In this paper, we consider the problem of scheduling n jobs with arbitrary release dates and due dates on a single machine, where job-processing times can be controlled by the allocation of a common resource, and the operation is modeled by a non-linear convex resource consumption function. The objective is to obtain an optimal processing permutation as well as an optimal resource allocation, such that all the jobs can be finished no later than their due dates, and the total resource consumption can be minimized. The problem is strongly NP- hard. A two-layer-structured algorithm based on the tabu-search is presented. The computational result, compared with that from a branch and bound algorithm, shows the algorithm is capable of producing optimal or near optimal solution for large-sized problems in an acceptable computational time.