Search Heuristics for a Parallel Machine Scheduling Problem with Ready Times and Due Dates

Abstract

We consider a problem of scheduling orders on identical parallel machines. An order can be released after the ready time and must be completed before the due date. An order is split into some batches and a batch is processed one of the parallel machines. The objective of the scheduling problem is to minimize the work-in-process holding costs of orders and the inventory holding costs of batches. We suggest two local search heuristics, simulated annealing and taboo search algorithms, to solve the problem. The performance of the suggested algorithms is reported through the computational tests on randomly generated test problems.