Abstract: Multiprocessor job scheduling of human-machine collaboration addresses the quantity requirements of workers and machines for each job,optimizes the resource allocation of workers and machines,determines job sequence,and thereby enables efficient collaborative operations.Based on the human-machine collaboration operations in coexistence and cooperation scenarios,with independent jobs processed at the same station and simultaneous jobs processed at different stations,a multiprocessor job scheduling problem was studied for coexistence and cooperation scenarios of human-machine collaboration,and a mixed integer programming model was established to minimize the makespan.The problem was proved to be strongly NP-hard.For the problem with one worker and two machines,an approximation algorithm was proposed with a worst-case performance ratio of 4/3,where simultaneous jobs were scheduled consecutively,and independent jobs were assigned according to the Longest Processing Time (LPT) rule.For the problem with h workers and m machines,another approximation algorithm was designed with a worst-case performance ratio of 2-1/(m+h),where following LPT rule,simultaneous jobs were first assigned to human-machine pairs,and independent jobs were then assigned to either workers or machines.Extensive simulation experiments demonstrated that the proposed algorithms achieved high-quality solutions with strong computational efficiency.

Key words: multiprocessor job scheduling, human-machine collaboration, approximation algorithm, worst-case performance ratio

摘要： 考虑人机协同的多处理机工件调度依据工件所需人和机器的数量,优化人机资源分配,决策工件加工顺序,实现作业高效协同。基于人机在同一工位独立加工的共存情形与人机在不同工位同时加工的合作情形,面向人机协同作业抽取出了考虑人机共存与合作的多处理机工件调度问题。以最小化最大完工时间为目标,建立了混合整数规划模型,证明了该问题是强NP困难问题。针对一人两机环境,先将需要人机同时加工的并行工件连续安排,再将仅需机器或人加工的独立工件依照最长加工时间优先规则安排,设计了最差性能比为4/3的近似算法;针对多人多机环境,通过人机配对形成人机组,依照最长加工时间优先规则,先将并行工件安排到人机组上,再将独立工件安排到人或机器上,设计了最差性能比为2－1/(m+h)的近似算法,其中m为机器数量,h为工人数量。通过大规模仿真实验,验证了所提算法在求解质量和计算效率上的有效性。

关键词: 多处理机工件调度, 人机协同, 近似算法, 最差性能比