A two-stage heuristic for single machine capacitated lot-sizing and scheduling with sequence-dependent setup costs
- Title
- A two-stage heuristic for single machine capacitated lot-sizing and scheduling with sequence-dependent setup costs
- Other Titles
- 작업순서 종속 작업준비 비용 및 용량제약을 고려한 단일기계 로트 크기 결정 및 일정계획 문제에 대한 연구
- Author
- 이동호
- Keywords
- Capacitated lot-sizing and scheduling; Sequence-dependent setup costs; Heuristics
- Issue Date
- 2011-10
- Publisher
- PERGAMON-ELSEVIER SCIENCE LTD, THE BOULEVARD, LANGFORD LANE, KIDLINGTON, OXFORD OX5 1GB, ENGLAND
- Citation
- COMPUTERS & INDUSTRIAL ENGINEERING,61(4),920-929
- Abstract
- This paper considers a single machine capacitated lot-sizing and scheduling problem. The problem is to determine the lot sizes and the sequence of lots while satisfying the demand requirements and the machine capacity in each period of a planning horizon. In particular, we consider sequence-dependent setup costs that depend on the type of the lot just completed and on the lot to be processed. The setup state preservation, i.e., the setup state at the end of a period is carried over to the next period, is also considered. The objective is to minimize the sum of setup and inventory holding costs over the planning horizon. Due to the complexity of the problem, we suggest a two-stage heuristic in which an initial solution is obtained and then it is improved using a backward and forward improvement method that incorporates various priority rules to select the items to be moved. Computational tests were done on randomly generated test instances and the results show that the two-stage heuristic outperforms the best existing algorithm significantly. Also, the heuristics with better priority rule combinations were used to solve case instances and much improvement is reported over the conventional method as well as the best existing algorithm. (C) 2011 Elsevier Ltd. All rights reserved.
- URI
- http://www.sciencedirect.com/science/article/pii/S0360835211001501?via%3Dihub
- ISSN
- 0360-8352
- DOI
- 10.1016/j.cie.2011.06.002
- Appears in Collections:
- COLLEGE OF ENGINEERING[S](공과대학) > INDUSTRIAL ENGINEERING(산업공학과) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML