A multi-period machine assignment problem |
| |
| Institution: | 1. Department of Industrial Engineering, Wright State University, 207 Russ Engineering Center, 3640 Colonel Glen Hwy, Dayton, OH 45435, United States;2. Graduate Program in Operations Research and Industrial Engineering, The University of Texas, ETC 5.160, C2200, Austin, TX 78712-1063, 512-471-3076, United States;1. Sorbonne Universités, UPMC Univ Paris 06 and CNRS, UMR 7606, LIP6, 75005 Paris, France;2. Eindhoven Institute of Technology, Netherlands;3. Institute of Computer Science, University of Wroc?aw, Poland;4. University of Santiago of Chile, Department of Industrial Engineering, Chile;1. Dipartimento di Ingegneria dell''Informazione, Università di Siena, Italy;2. Dipartimento di Ingegneria dell''Informazione, Università di Siena, Via Roma 56, 53100, Italy;3. Laboratoire d''Informatiqued′Informatique – Polytech''Tours, Université de Tours, France;1. Institute of Information Management, Department of Information Management and Finance, National Chiao Tung University, Taiwan;2. School of Mathematical and Physical Sciences, University of Technology Sydney, Ultimo 2007, Australia;1. Département de mathématiques et de génie industriel, École Polytechnique, Montréal, Canada;2. Service de l?enseignement des méthodes quantitatives de gestion, HEC, Montréal, Canada |
| |
| Abstract: | In this paper, a multi-period assignment problem is studied that arises as part of a weekly planning problem at mail processing and distribution centers. These facilities contain a wide variety of automation equipment that is used to cancel, sort, and sequence the mail. The input to the problem is an equipment schedule that indicates the number of machines required for each job or operation during the day. This result is then post-processed by solving a multi-period assignment problem to determine the sequence of operations for each machine. Two criteria are used for this purpose. The first is to minimize the number of startups, and the second is to minimize the number of machines used per operation.The problem is modeled as a 0–1 integer program that can be solved in polynomial time when only the first criterion is considered. To find solutions in general, a two-stage heuristic is developed that always obtains the minimum number of startups, but not necessarily the minimum number of machines per operation. In a comparative study, high quality solutions were routinely provided by the heuristic in negligible time when compared to a commercial branch-and-bound code (Xpress). For most hard instances, the branch-and-bound code was not able to even find continuous solutions within acceptable time limits. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
