title: Single machine scheduling and due date assignment with past-sequence-dependent setup time and position-dependent processing time.
abstract: This paper considers single machine scheduling and due date assignment with setup time. The setup time is proportional to the length of the already processed jobs; that is, the setup time is past-sequence-dependent (p-s-d). It is assumed that a job's processing time depends on its position in a sequence. The objective functions include total earliness, the weighted number of tardy jobs, and the cost of due date assignment. We analyze these problems with two different due date assignment methods. We first consider the model with job-dependent position effects. For each case, by converting the problem to a series of assignment problems, we proved that the problems can be solved in O(n(4)) time. For the model with job-independent position effects, we proved that the problems can be solved in O(n(3)) time by providing a dynamic programming algorithm.
authors.affiliation: College of Mathematics and Systems Sciences, Shenyang Normal University, Shenyang, Liaoning 110034, China.
authors.forename: Chuan-Li
authors.initials: CL
authors.lastname: Zhao
authors.affiliation: Department of Industrial Management, Nan Kai University of Technology, Nantou 542, Taiwan.
authors.forename: Chou-Jung
authors.identifier: 0000-0003-0803-3504
authors.initials: CJ
authors.lastname: Hsu
authors.affiliation: Department of Industrial Management, Nan Kai University of Technology, Nantou 542, Taiwan.
authors.forename: Hua-Feng
authors.initials: HF
authors.lastname: Hsu
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D004526:Efficiency; D006801:Humans; D008962:Models, Theoretical; D015203:Reproducibility of Results; D013997:Time Factors; D017748:Time Management / Q000379:methods*