This paper models the scheduling of one type of flexible transfer line as an integer programming problem.Since the integer program falls within the NP class of problems, then its complexity increases exponentially as ...This paper models the scheduling of one type of flexible transfer line as an integer programming problem.Since the integer program falls within the NP class of problems, then its complexity increases exponentially as theproblem size increases, making the problem intractable even for a medium size system. An approximate algorithm,whose complexity only increases algebraically with the problem size, is presented to obtain suboptimal solutions ofscheduling problems. Numerical experiments indicate that the suboptimal solution is near to the optimal solution inthe general case where the neighboring points are dense around the optimal solution in the feasible ration of the integer program.展开更多
文摘This paper models the scheduling of one type of flexible transfer line as an integer programming problem.Since the integer program falls within the NP class of problems, then its complexity increases exponentially as theproblem size increases, making the problem intractable even for a medium size system. An approximate algorithm,whose complexity only increases algebraically with the problem size, is presented to obtain suboptimal solutions ofscheduling problems. Numerical experiments indicate that the suboptimal solution is near to the optimal solution inthe general case where the neighboring points are dense around the optimal solution in the feasible ration of the integer program.