The scheduling problem on a single batching machine with family jobs was proposed.The single batching machine can process a group of jobs simultaneously as a batch.Jobs in the same batch complete at the same time.The ...The scheduling problem on a single batching machine with family jobs was proposed.The single batching machine can process a group of jobs simultaneously as a batch.Jobs in the same batch complete at the same time.The batch size is assumed to be unbounded.Jobs that belong to different families can not be processed in the same batch.The objective function is minimizing maximum lateness.For the problem with fixed number of m families and n jobs,a polynomial time algorithm based on dynamic programming with time complexity of O(n(n/m+1)m)was presented.展开更多
基金National Natural Science Foundation of China(No.70832002)Graduate Student Innovation Fund of Fudan University,China
文摘The scheduling problem on a single batching machine with family jobs was proposed.The single batching machine can process a group of jobs simultaneously as a batch.Jobs in the same batch complete at the same time.The batch size is assumed to be unbounded.Jobs that belong to different families can not be processed in the same batch.The objective function is minimizing maximum lateness.For the problem with fixed number of m families and n jobs,a polynomial time algorithm based on dynamic programming with time complexity of O(n(n/m+1)m)was presented.
