Three parallel task assignment problems with shared resources

Abstract

We study three optimization problems in which non-renewable resources are used to execute tasks in parallel. Problems differentiate by the assumptions of whether a resource can be shared between several tasks or not, or whether resource sharing between the tasks is limited. We present very efficient solution procedures for two of these problems and prove that the third problem is NP-hard in the strong sense and that it can be solved efficiently for special cases. Applications include optimal resource allocation problems in labor-intensive cellular manufacturing and in parallel task computing.

Keywords:

• Resource allocation
• computational complexity
• polynomial algorithms
• cellular manufacturing
• parallel task computing

Additional information

Notes on contributors

Ali Diabat

Dr. Ali Diabat is a Global Network Professor of Engineering at New York University Abu Dhabi. His research focuses on different applications of optimization and operations research: in particular, logistics and supply chain management, healthcare management, and production planning. He has published over 100 research journal papers and over 30 conference papers in leading journals and international conference proceedings, and his research has received about 5 million dollars of grant funding from different industries and collaborative proposals with academic institutions. Dr. Diabat has received several Excellence in Teaching awards, including an Outstanding Graduate Instructor Award and an Excellence in Teaching Award from Purdue University, in 2004 and 2006, respectively. He was the recipient of the 2012 Excellence in Teaching Award from Masdar Institute, and in 2014, he also received the Best Faculty Research Award from the Department of Engineering Systems and Management at Masdar Institute. Dr. Diabat currently serves as an associate editor of the Journal of Manufacturing Systems, an area editor of the Journal of Computers and Industrial Engineering, and an engineering editor of the Arabian Journal for Science and Engineering.

Alexandre Dolgui

Dr. Alexandre Dolgui is a Distinguished Professor and the Head of the Automation, Production, and Computer Sciences Department at the IMT Atlantique campus in Nantes, France. His research focuses on manufacturing line design, production planning and scheduling, and supply chain engineering. His main results are based on exact mathematical programming methods and their intelligent coupling with heuristics and metaheuristics algorithms. He has contributed to the theory of assembly line balancing, combinatorial design of machining lines, process planning, supply chain scheduling, lot-sizing and replenishment under uncertainties. He is the editor-in-chief of the International Journal of Production Research, an area editor of Computers & Industrial Engineering, a member of the editorial boards for several other journals, including the International Journal of Production Economics, Fellow of the European Academy for Industrial Management, Member of the Board of the International Foundation for Production Research, former Chair of IFAC TC 5.2 Manufacturing Modelling for Management and Control, and Member of IFIP WG 5.7 Advances in Production Management Systems.

Władysław Janiak

Władysław A. Janiak (Ph.D.Eng) is President of the Management Board and CEO at Wandix Ltd. He runs his own smart solutions consulting company and is also a staff worker at WSB University in Wrocław. He has published in top operational research, computer science, and industrial research journals. His research interests are in operational research, computer science, management, organizational structures, and marketing.

Mikhail Y. Kovalyov

Professor Mikhail Y. Kovalyov is a Deputy General Director for Research of the United Institute of Informatics Problems (Minsk, Belarus) and a corresponding member of the National Academy of Sciences of Belarus. He has contributed to the theoretical frameworks of fully polynomial approximation schemes, batch scheduling, computer scheduling, production line balancing, computational complexity and combinatorial algorithm design, production and transport logistics. He has published in top operational research, computer science, and industrial research journals and he is involved in the editorial work of the journals Computers and Operations Research, European Journal of Operational Research, INFORMS Journal on Computing, Omega, and Journal of Scheduling.