Search the World's Largest Database of Information Science & Technology Terms & Definitions
InfInfoScipedia LogoScipedia
A Free Service of IGI Global Publishing House
Below please find a list of definitions for the term that
you selected from multiple scholarly research resources.

What is NP-Hard Problem (Non-Deterministic-Polynomial problem)

Chapter 17
Handbook of Research on Industrial Applications for Improved Supply Chain Performance
Concept of computational complexity theory to establish “how difficult it is to solve a problem using an algorithm”. The problem A is considered NP-hard when every problem B in NP can be reduced (converted) to A. The reduction allows to establish that problem A is as difficult to solve as problem B. If there is a deterministic algorithm T that solves the problem A in a time bounded by a polynomial, then the same algorithm will solve the problem B in a time bounded by a polynomial ( Dasgupta, Papadimitriou & Vazirani, 2006 ).
Published in Chapter:
An Analysis of the Traveling Speed in the Traveling Hoist Scheduling Problem for Electroplating Processes
José Itzcoatl Gomar-Madriz (Tecnológico Nacional de México en Celaya, Mexico), Salvador Hernandez-González (Tecnológico Nacional de México en Celaya, Mexico), and Jaime Navarrete-Damián (Centro Regional de Optimización y Desarrollo de Equipo de Celaya, Mexico)
Copyright: © 2020 |Pages: 20
DOI: 10.4018/978-1-7998-0202-0.ch017
Abstract
The Hoist Scheduling Problem is combinatory, so tools such as mathematical programming need to be used to get the sequence of movements, respecting the constraints of the process by minimizing the cycle time. A sequence in which the order of movements follows the order of the process is known as the basic diagram. These schedules do not have any clearance for the hoist to make any other movements, resulting in a loss in productivity. This chapter takes the production line of a Mexican factory as a case study, analyzing the hoist's travelling speed to find sequences of movements that could improve productivity. The results of the study indicate that the cycle time has a nonlinear behavior in respect of the hoist's travelling speed and it was determined that there are travelling speeds for which sequences are obtained with enough clearance to make other movements and keep other carriers on the line. A suitable speed was estimated in the case.
Full Text Chapter Download: US $37.50 Add to Cart
eContent Pro Discount Banner
InfoSci OnDemandECP Editorial ServicesAGOSR