AN EXACT PARALLEL ALGORITHM FOR SCHEDULING WHEN PRODUCTION COSTS DEPEND ON CONSECUTIVE SYSTEM STATES

An exact parallel algorithm is presented for determining schedules when costs depend on consecutive jobs passed through a production system and there is a benefit associated with each job. Optimal schedules are found for the cases when the production goals are to: (i) maximize benefits minus costs; (ii) minimize costs; (iii) maximize benefits while keeping costs below a prescribed level; or (iv) minimize costs while attaining some level of benefits. Determining optimal schedules with any of the four production goals is shown to be equivalent to the prize collecting traveling salesman problem. The algorithm uses a branch and bound approach based on lower bounds derived from a modified assignment problem, branching rules that partition the search space, and an upper bounding procedure based on subtour patching. The algorithm is implemented on a shared-memory multiprocessor and computational results are presented for problems ranging in size from 50 to 200 jobs (cities). © 1990.