Sequencing precedence-related jobs on two machines to minimize the weighted completion time

We address the problem P2|prec|∑wjCj. The problem is known to be NP-hard. We offer a binary integer program (BIP) and a dynamic program (DP); the latter is based on the concept of “initial subsets” of jobs and the optic of “weighted earliness-tardiness”. Although the DP approach expands the size of problems that can be solved to optimality to almost twice that obtained by the BIP, it reaches its computational limit around 25 jobs with mean job processing time of 10. We then introduce a genetic algorithm (GA) procedure that is capable of solving any problem size, and further extends the domain of applicability to more than two machines in parallel (problem Pm|prec|∑wjCj). The BIP is used also to establish a good lower bound against which the performance of the GA procedure is measured for larger size problems. Experimental investigation of the GA procedure demonstrates that it is capable of achieving the optimum in very few iterations (less than 20), thanks to the manner in which the initial population is generated, and that early abortion still yields excellent approximation to the optimum as judged by its proximity to the lower bound.