 Minimizing the sum of job completion times on capacitated two-parallel machinesChing-Jong Liao, Chien-Wen Chao and Chien-Hung Lin European Journal of Operational Research, 2009, vol. 197, issue 2, 475-481 Abstract: This paper considers a scheduling problem with two identical parallel machines. One has unlimited capacity; the other can only run for a fixed time. A given set of jobs must be scheduled on the two machines with the goal of minimizing the sum of their completion times. The paper proposes an optimal branch and bound algorithm which employs three powerful elements, including an algorithm for computing the upper bound, a lower bound algorithm, and a fathoming condition. The branch and bound algorithm was tested on problems of various sizes and parameters. The results show that the algorithm is quite efficient to solve all the test problems. In particular, the total computation time for the hardest problem is less than 0.1second for a set of 100 problem instances. An important finding of the tests is that the upper bound algorithm can actually find optimal solutions to a quite large number of problems. Keywords: Parallel; machine; scheduling; Availability; constraints; Branch; and; bound; algorithm (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:197:y:2009:i:2:p:475-481 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.