Approximate Solution to the Scheduling of Flexible Transfer Lines

ＡｐｐｒｏｘｉｍａｔｅＳｏｌｕｔｉｏｎｔｏｔｈｅＳｃｈｅｄｕｌｉｎｇｏｆＦｌｅｘｉｂｌｅＴｒａｎｓｆｅｒＬｉｎｅｓ￥ＹａｎｇＳｈｅｎｇ，ＷｕＣｈｅｎｇ杨盛，吴澄（ＣＩＭＳ－ＥＲＣ，ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｂｅｌｉｉｎｇ１０００８４）Ａｂ...

Approximate Solution to the Scheduling of Flexible Transfer Lines

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.