In this paper we extend some well-known notions of combinatorics on multi-sets such as iterative permutation, multi-subset, iterative combination and then construct new efficient algorithms for generating all iterative permutations, multi-subsets and iterative combinations of a multi-set. Applying the parallelizing method based on output decomposition we parallelize the algorithms. Furthermore, we use these algorithms to solve an optimal problem of work arrangement and an extended knapsack one.