On generalized movement scheduling problem
Lilu Pan · Lincoln (University of Nebraska) · 1988
The problems of generalized movement scheduling (GMS) and its dual, the minimum pace length problem (MPL), are defined and investigated. In the generalized movement model a set of objects are to be scheduled to move from their individual sources to their individual destinations in a transportation network. The continuous moving time of each object is limited and the objects have to move and rest alternatively. Each object has a deadline. The objective of the GMS problem is, to find a schedule such that all the objects meet their deadline given the speed, moving and resting intervals of the objects. The objective of the MPL problem is, given the moving speed of an object and the number of moving intervals, find the minimum moving interval for the object to reach its destination. When a number of objects need to rest on a same station simultaneously but the rest station can not accommodate all of them in a time, a node conflict happens. It is proved that if the node conflict is considered, the GMS problem is NP-complete. An optimal polynomial algorithm is developed for the GMS problem without node conflict. In the MPL problem, if the speed of object differs in different intervals, the problem is proved to be NP-complete. An optimal polynomial algorithm is developed to find the minimum interval for the case when the speed of the object is feed. Heuristic algorithms are developed and analyzed for the intractable cases of the GMS and MPL problems.