51. Algorithms for common due-date assignment and sequencing on a single machine with sequence-dependent setup times
- Author
-
Dong-Ho Lee and J.-G. Kim
- Subjects
Marketing ,021103 operations research ,Sequence-dependent setup ,Branch and bound ,Job shop scheduling ,Heuristic ,Computer science ,Strategy and Management ,Tardiness ,0211 other engineering and technologies ,02 engineering and technology ,Management Science and Operations Research ,Upper and lower bounds ,Management Information Systems ,Scheduling (computing) ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Algorithm ,Assignment problem ,Generalized assignment problem ,Weapon target assignment problem - Abstract
This paper focuses on the single machine sequencing and common due-date assignment problem for the objective of minimizing the sum of the penalties associated with earliness, tardiness and due-date assignment. Unlike the previous research articles on this class of scheduling problem, we consider sequence-dependent setup times that make the problem much more difficult. To solve the problem, a branch and bound algorithm, which incorporates the method to obtain lower and upper bounds as well as a dominance property to reduce the search space, is suggested that gives the optimal solutions for small-sized instances. Heuristic algorithms are suggested to obtain solutions for large-sized problems within a reasonable computation time. The performances of both the optimal and heuristic algorithms, in computational experiments on randomly generated test instances, are reported.
- Published
- 2009