An　assembly　line　is　an　industrial　arrangement　of　machines,　equipments　and　operators　for　continuous　flow　of　work-pieces　in　mass-production　operations.　Recently,　the　reliability　of　assembly　production　has　been　investigated　by　taking　into　account　task　time　uncertainties.　This　paper　provides　a　new　reliability　metric　which　encompasses　two　types　of　task　time　uncertainties.　A　multi-objective　mathematical　model　was　developed　to　maximize　the　reliability　and　efficiency　of　assembly　lines.　Neighborhood　search　methods　with　two　restart　mechanisms　are　devised　to　solve　the　model　and　they　are　compared　in　a　numerical　study.　Further,　the　results　show　some　managerial　implications　for　the　production　planners.　The　methodology　proposed　in　this　research　can　be　applied　to　many　industries　when　some　historical　data　of　uncertain　inputs　are　available　and　some　are　not.