For the CCMK and the CCBP problems we present polynomial time approximation schemes. Optimal algorithms are presented for the CCMK and FPP problems with identical knapsacks and unit-sized items. The talk is based on my Ph. May 2001 Gates Building 498. We consider the following natural scheduling problem.
Jobs arrive over time to be scheduled on a single machine.
Each job has a processing time and a weight. We seek to minimize the sum of weighted flow times of the jobs. The flow time of a job is the overall time the job spends in the system from the time it arrives to the time its processing is completed. We allow preemption of jobs. Here P is the ratio of the maximum job size to the minimum job size.