Solution algorithms for the makespan minimization problem with the general learning model |
| |
Authors: | Adam Janiak Wadysaw Adam Janiak Radosaw Rudek Agnieszka Wielgus |
| |
Affiliation: | aInstitute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Janiszewskiego 11/17, 50-372 Wrocław, Poland;bFaculty of Computer Science and Management, Wrocław University of Technology, Łukasiewicza 5, 50-371 Wrocław, Poland |
| |
Abstract: | Most of the papers devoted to scheduling problems with the learning effect concern the Wright’s learning curve. On the other hand, the study about learning has pointed out that the learning curve in practice is very often an S-shaped function, which has not been considered in scheduling. Thus, in this paper, a single processor makespan minimization problem with an S-shaped learning model is investigated. We prove that this problem is strongly NP-hard even if the experience provided by each job is equal to its normal processing time. Therefore, to solve this problem, we prove some eliminating properties that are used to construct a branch and bound algorithm and some fast heuristic methods. Since the proposed algorithms are dedicated for the general case, i.e., where job processing times are arbitrary non-increasing experience dependent functions, their efficiency is verified numerically for the S-shaped model. |
| |
Keywords: | Scheduling Learning effect Single processor Computational complexity Branch and bound Heuristic |
本文献已被 ScienceDirect 等数据库收录! |
|