Just-in-time scheduling with controllable processing times on parallel machines |
| |
Authors: | Yaron Leyvand Dvir Shabtay George Steiner Liron Yedidsion |
| |
Institution: | 1.Department of Industrial Engineering and Management,Ben-Gurion University of the Negev,Beer-Sheva,Israel;2.Operations Management Area, DeGroote School of Business,McMaster University,Hamilton,Canada;3.Faculty of Industrial Engineering and Management,Technion—Israel Institute of Technology,Haifa,Israel |
| |
Abstract: | We study scheduling problems with controllable processing times on parallel machines. Our objectives are to maximize the weighted
number of jobs that are completed exactly at their due date and to minimize the total resource allocation cost. We consider
four different models for treating the two criteria. We prove that three of these problems are
NP\mathcal{NP}
-hard even on a single machine, but somewhat surprisingly, the problem of maximizing an integrated objective function can
be solved in polynomial time even for the general case of a fixed number of unrelated parallel machines. For the three
NP\mathcal{NP}
-hard versions of the problem, with a fixed number of machines and a discrete resource type, we provide a pseudo-polynomial
time optimization algorithm, which is converted to a fully polynomial time approximation scheme. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|