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

Amaddeo, H.F. and Nawijn, W.M. and Harten van, A. (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

Preview

PDF
720Kb

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:	Operations Management and Logistics (OMPL)
Research Group:	Industrial Engineering & Business Information Systems (IEBIS)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 140770