Multiprocessor scheduling for variable length tasks

The Variable Length Multiprocessor Scheduling Problem (VLMSP) is studied. It is based on the Variable Length Sequencing Problem (VLSP), which is proposed by Czumaj et al. and motivated by efficient information gathering over the web. The decision version of VLMSP is proved to be NP-hard and an approximation algorithm with factor a<4 for an optimization version of maximizing the number of completed tasks is presented.