Thek-track assignment problem is a scheduling problem withnjobs andkmachines. Each machinejhas a certain operational period (track) which starts at timeajand ends at timebj. Each jobihas a specific start timesiand a specific finish timeti. A schedule is an assignment of certain jobs to machines such that the intervals si,tiassigned to the same machinejdo not overlap and fit into track aj,bj. We are interested in a schedule which maximizes the number of assigned jobs. AO(nk−1k!kk+1)-algorithm which solves this problem is presented. Furthermore it is shown that the more general problem, in which for each track only a given set of jobs can be scheduled on that track, can be solved inO(nkk!kk)-tim
展开▼
