Single-machine scheduling for minimizing total cost under nonnegative condition of starting time

A single-machine scheduling method is proposed for minimizing the total cost consisting of flowtime cost and asymmetric penalty cost of earliness-tardiness, when all jobs have a relatively small common due date and an identical cost function. In this case, it is necessary to schedule jobs so that the starting time of the first job is nonnegative. Dominance conditions necessary for an optimal schedule are derived to this constrained scheduling problem. An algorithm based on these conditions is proposed to find an optimal schedule. Numerical examples are demonstrated to show the effectiveness of the proposed method. [In Japanese.]