On scheduling around large restrictive common due windows |
| |
| Affiliation: | 1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China;2. Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing, China;1. Institute of Computer Science, University of Osnabrück, 49069 Osnabrück, Germany;2. Department of Informatics, Technical University of Munich, 80333 Munich, Germany;1. The University of Sydney Business School, Sydney, NSW 2006, Australia;2. Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel;3. Operations Management Area, DeGroote School of Business, McMaster University, Hamilton, Ontario, Canada |
| |
| Abstract: | This paper deals with the problem of scheduling a number of jobs on a single machine around a large, restrictive common due window. We consider individual earliness and tardiness penalties for the jobs. The objective is to find an optimal schedule which jointly minimizes the sum of the earliness and tardiness penalties. This problem is intractable and hence no efficient procedure for solving large instances is expected to be found. For this reason we first introduced a mapping of the problem which takes advantage of the structural properties inherent to optimal solutions. Secondly we solved the problem under study by using this mapping and applying three meta-heuristics, namely evolutionary strategy, simulated annealing and threshold accepting. To validate the quality of these approaches, altogether 250 benchmark problems with different window sizes and positions of up to 200 jobs are examined. Furthermore small instances are solved to optimality by a mixed integer programming formulation. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
