首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Approximation schemes for job shop scheduling problems with controllable processing times
Institution:1. Universität zu Kiel, Christian-Albrechts Platz 4, D-24198 Kiel, Germany;2. IDSIA––Istituto Dalle Molle di Studi sull'' Intelligenza Artificiale, Galleria 2, Manno 6928 Lugano, Switzerland;3. Department of Computer Science, The University of Western Ontario, London, ON, N6A 5B7 Canada;1. Sorbonne Université, Centre National de la Recherche Scientifique, UMR 7190, Institut Jean le Rond d''Alembert, F-75005 Paris, France;2. LIMSI, CNRS, Université Paris-Saclay, Campus universitaire bât 508, Rue John von Neumann, F-91405 Orsay Cedex, France;3. INRIA Saclay, Gamma3 Project, F-91126 Palaiseau, France;1. School of Transportation Science and Engineering, Beijing Key Laboratory for Cooperative Vehicle Infrastructure Systems and Safety Control, Beihang University, Beijing 100191, China;2. School of Transportation and Logistics, Dalian University of Technology, Dalian 116024, China;1. Department of Mathematics, Hill Center, Busch Campus, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ 08854, USA;2. Departments of Mathematics and Computer Science, Technion, Israel Institute of Technology, 32000 Haifa, Israel;3. Laboratoire Jacques-Louis-Lions, Université Pierre-et-Marie-Curie, 4, place Jussieu, 75252 Paris cedex 05, France;4. Dpto. de Matemática Aplicada, Universidad Complutense de Madrid, Spain;5. Instituto de Matemática Interdisciplinar, Universidad Complutense de Madrid, Spain;1. Software School, Dalian University of Technology, Dalian 116620, China;2. Dalian Neusoft Institute of Information, China
Abstract:In this paper we study the job shop scheduling problem under the assumption that the jobs have controllable processing times. The fact that the jobs have controllable processing times means that it is possible to reduce the processing time of the jobs by paying a certain cost. We consider two models of controllable processing times: continuous and discrete. For both models we present polynomial time approximation schemes when the number of machines and the number of operations per job are fixed.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号