One-machine job-scheduling with non-constant capacity - Minimizing weighted completion times

Share/Save/Bookmark

Amaddeo, H.F. and Nawijn, W.M. and Harten, A. van (1997) One-machine job-scheduling with non-constant capacity - Minimizing weighted completion times. European Journal of Operational Research, 102 (3). pp. 502-512. ISSN 0377-2217

[img]
Preview
PDF
737kB
Abstract:In this paper an n-job one-machine scheduling problem is considered, in which the machine capacity is time-dependent and jobs are characterized by their work content. The objective is to minimize the sum of weighted completion times. A necessary optimality condition is presented and we discuss some special cases where this condition is also sufficient. We prove that the problem is NP-complete. A branch-and-bound algorithm is developed for the case when the capacity function is a step function. Computational results for 1000 test problems are presented.
Item Type:Article
Copyright:© 1997 Elsevier Science
Research Chair:
Research Group:
Link to this item:http://purl.utwente.nl/publications/30131
Official URL:http://dx.doi.org/10.1016/S0377-2217(96)00240-8
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 140770