\input zb-basic
\input zb-ioport
\iteman{io-port 05142339}
\itemau{Nessah, Rabia; Chu, Chengbin; Yalaoui, Farouk}
\itemti{An exact method for $Pm/sds, r_{i}/ \sum^{n}_{i=1} C_{i}$ problem.}
\itemso{Comput. Oper. Res. 34, No. 9, 2840-2848 (2007).}
\itemab
Summary: This paper addresses an identical parallel machine scheduling problem, with sequence-dependent setup times and release dates to minimize total completion time. This problem is known to be strongly NP-hard. We prove a sufficient and necessary condition for local optimality which can also be considered as a priority rule. We then define a dominant subset based on this condition. We present efficient heuristic algorithms using this condition to build a schedule belonging to this subset. We also prove a dominance theorem, and develop a lower bound that can be computed in polynomial time. We construct a branch-and-bound algorithm in which the heuristic, the lower bound and the dominance properties are incorporated. Computational experiments suggest that the algorithm can handle test problems with 40 jobs and 2 machines.
\itemrv{~}
\itemcc{}
\itemut{identical parallel machine; scheduling; setup time; release dates; lower bound; dominance properties; heuristic}
\itemli{doi:10.1016/j.cor.2005.10.017}
\end