| Article ID: | iaor20101722 |
| Volume: | 38 |
| Issue: | 2 |
| Start Page Number: | 123 |
| End Page Number: | 126 |
| Publication Date: | Mar 2010 |
| Journal: | Operations Research Letters |
| Authors: | Choi Byung-Cheon, Leung Joseph Y-T, Pinedo Michael L |
We consider the problem of scheduling a set of independent jobs on a single machine so as to minimize the total weighted completion time, subject to the constraint that the total compression cost is less than or equal to a fixed amount. The complexity of this problem is mentioned as an open problem. In this note we show that the problem is NP-hard.