Minimizing makespan in a multimode multiprocessor shop scheduling problem
研究了在专用处理器上多模式调度任务以最小化最大完工时间的问题，提出了基于部分调度的新启发式算法，并推导了不同下界，通过随机测试问题评估了算法性能。
We study the problem of multimode scheduling tasks on dedicated processors, with the objective of minimizing the maximum completion time. Each task can be undertaken in one among a set of predefined alternative modes, where each mode specifies a required set of dedicated processors and a processing time. At any time each processor can be used by a single task at most. General precedence constraints exist among tasks, and task preemption is not allowed. The problem consists of assigning a mode and a starting time to each task, respecting processor and precedence constraints, to minimize the time required to complete all tasks. The problem is NP-hard in several particular cases. In previous works, we studied algorithms in which a solution was obtained by means of an iterative procedure that combines mode assignment and sequencing phases separately. In this paper, we present some new heuristics where the decision on the mode assignment is taken on the basis of a partial schedule. Then, for each task, the mode selection and the starting time are chosen simultaneously considering the current processor usage. Different lower bounds are derived from a mathematical formulation of the problem and from a graph representation of a particular relaxed version of the problem. Heuristic solutions and lower bounds are evaluated on randomly generated test problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 893–911, 1999