New results on single-machine scheduling with past-sequence-dependent delivery times

Scheduling with past-sequence-dependent (psd) delivery times is motivated by questions that arise in the electronic manufacturing industry: an electronic component may be exposed to certain a electromagnetic field while waiting for processing and is required to neutralize the effect of electromagnetism. The time spent on the neutralization process has been modeled as psd delivery time in the literature. In this paper, we consider single-machine scheduling problems with psd delivery times. We respectively derive polynomial algorithms for the following objective functions: the minimization of the total weighted completion time, the total weighted discounted completion time, the total absolute differences in completion times and the sum of earliness, tardiness and common due date penalty. At last, for the criteria of minimization the total weighted tardiness, we propose a polynomial algorithm to optimally solve the problem under a certain condition. (C) 2012 Elsevier B.V. All rights reserved.