精华内容
下载资源
问答
  • 任务分配算法

    2014-03-16 23:38:22
    当有n个人选择N个任务的时候,通过成本矩阵,采用回溯法达到最优任务分配,使得任务的总成本最小
  • 基于分数激励机制的无线传感器网络任务分配算法
  • 针对无线传感器网络任务调度的实时性及节点计算及能量受限的特点,根据任务截止期赋予任务优先级,优先考虑高优先级任务,设计了一个无线传感器网络中带复杂联盟的自适应任务分配算法。为尽最大努力确保任务在截止期...
  • 供应链运作计划模型及其任务分配算法研究,祝勇,王正肖,本文通过研究在多供应商和多加工工厂环境下供应链运作模型,提出了考虑总成本时的供应链任务分配模式,基于优先策略构造了供应链
  • 传感器网络的某些应用,要求系统生命期必须达到数月、甚至数年。...首先对传感器网络的任务分配问题建模,并基于遗传算法和模拟退火法提出了传感器网络GaSA任务分配算法,最后对算法进行仿真实验,验证了算法的有效性。
  • 任务分配算法,主要是轮询然后是 MAP利用数据结构, KEY里封装对象 再追加list 如 Map<String, List<String>> old_map = new HashMap(); old_map.get(same.getIsoCode()).add(nodeSame.getCountryIp...

    任务分配算法,主要是轮询然后是 MAP利用数据结构, KEY里封装对象 再追加list  如 

    Map<String, List<String>> old_map = new HashMap();
    old_map.get(same.getIsoCode()).add(nodeSame.getCountryIp());

    对于任务分配 非常有帮助

    /*
     * Zenlayer.com Inc.
     * Copyright (c) 2014-2019 All Rights Reserved.
     */
    package com.zenlayer.ad.nodetool;
    
    import com.maxmind.geoip2.DatabaseReader;
    import com.maxmind.geoip2.exception.GeoIp2Exception;
    import com.maxmind.geoip2.model.CityResponse;
    import com.maxmind.geoip2.record.City;
    import com.maxmind.geoip2.record.Continent;
    import com.maxmind.geoip2.record.Country;
    import com.maxmind.geoip2.record.Location;
    import com.maxmind.geoip2.record.Postal;
    import com.maxmind.geoip2.record.Subdivision;
    import com.zenlayer.ad.jedis.RedisClient;
    import com.zenlayer.ad.mapper.SnmpMapper;
    import com.zenlayer.util.DataTransformation;
    import org.apache.commons.lang3.StringUtils;
    import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.stereotype.Component;
    
    import javax.annotation.Resource;
    import java.io.File;
    import java.io.IOException;
    import java.net.InetAddress;
    import java.net.UnknownHostException;
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    import java.util.stream.Collectors;
    
    /**
     * @author jack.li
     * @date 2019-10-30 18:07:30
     * @version $ Id: NodeToolService.java, v 0.1  admin Exp $
     *<1> 采用新的分配节点任务,按区域划分,通过IP自动获取所在地区 (BMC 交换机的分配方式)
     *
     *<2> 按着IP,平均分配到所有存活的节点上
     */
    @Component("nodeToolService")
    public class NodeToolService {
    
        @Resource
        RedisClient redisclient;
        @Autowired
        private SnmpMapper snmpMapper;
        @Autowired
        NodeIdcService nodeIdcService;
    
        //默认洛杉机的节点,备份采集所有失败的交换机
        public static String laxIp = "68.8.8.194";
    
        public boolean getSnmpAll() throws IOException, GeoIp2Exception {
    
            //1 所有内网IP 不进行地址解析, 2 另外分配所有失败交换机的备选节点
            List<Map<String, Object>> innerAllIpList = new ArrayList<>();
    
            //所有公网IP,需要解析地区位置,分配采集任务
            List<Map<String, Object>> publicIp = new ArrayList<>();
    
            //采集服务注册的IP,往这里分配交换机IP
            List<CountryModel> nodelist = new ArrayList<>();
    
            //中国的IP,记录下来,跳过此IP去分配内网IP,用LIST防止有多个中国服务器
            List<String> cn_ip_list = new ArrayList();
    
            Map<String, List<Map<String, Object>>> snmpAll = new HashMap<>();
    
            Map<String, List<Map<String, Object>>> bmclist = null;
            Map<String, List<Map<String, Object>>> idclist = null;
            try {
                AllIplistTask(publicIp, innerAllIpList, nodelist, cn_ip_list);
                if (publicIp.size() > 0 && nodelist.size() > 0) {
                    bmclist = nodeIPtask(publicIp, innerAllIpList, nodelist, cn_ip_list);
                }
                if (nodelist.size() > 0) {
                    idclist = nodeIdcService.getIdcNodeService(nodelist, innerAllIpList);
                    nodelist.stream().forEach(countryModel -> {
                        snmpAll.put(countryModel.getCountryIp(), new ArrayList<>());
                    });
                    bmclist.forEach((k, v) -> {
                        snmpAll.get(k).addAll(v);
                    });
                    idclist.forEach((k, v) -> {
                        snmpAll.get(k).addAll(v);
                    });
                    snmpAll.forEach((s, maps) -> {
                        // JSONArray arraylist = new JSONArray(Collections.singletonList(maps));
                        redisclient.set(s, DataTransformation.parseListForMapsToJsonArrayStr(maps).toJSONString(), 0);
                        //System.out.println(DataTransformation.parseListForMapsToJsonArrayStr(maps).size());
                    });
                }
                //内网地直 直接分配到洛杉机,采集专用所有
                if (innerAllIpList.size() > 0) {
                    redisclient.set(laxIp, DataTransformation.parseListForMapsToJsonArrayStr(innerAllIpList).toJSONString(), 0);
                }
                System.out.println("====================================:SNMP任务调度结束:====================================:");
            } catch (IOException e) {
                e.printStackTrace();
                return false;
            }
            return true;
    
        }
    
        //封装所有IP区域 过滤的方法
        public void AllIplistTask(List publicIps, List innerAllIpList, List nodelists, List cn_ip_lists) throws IOException {
    
            File database = getFileGeo();
    
            DatabaseReader reader = new DatabaseReader.Builder(database).build();
            List<Map<String, Object>> countryList = new ArrayList<>();
    
            List<Set<Map<String, Object>>> listset = new ArrayList(snmpMapper.getSnmpList());
    
            List<Map<String, Object>> list = new ArrayList(listset);
    
            //过滤掉所有为空的IP
            List<Map<String, Object>> filtelistIP = null;
            filtelistIP = list.stream().filter(smap -> null != smap.get("ip") && !"".equals(smap.get("ip"))).collect(Collectors.toList());
    
            //所有公网IP,需要解析地区位置,分配采集任务
            List<Map<String, Object>> publicIp = publicIps;
    
            filtelistIP.stream().forEach(filterIP -> {
                if (internalIp(filterIP.get("ip").toString())) {
                    //  innerAllIpList.add(filterIP);// 暂时去掉内网地址
                } else {
                    publicIp.add(filterIP);
                }
            });
    
            publicIp.stream().forEach(imp -> {
                try {
                    InetAddress ipAddress = InetAddress.getByName(imp.get("ip").toString());
                    CityResponse response = reader.city(ipAddress);
                    Continent continent = response.getContinent();
                    Country country = response.getCountry();
    
                    imp.put("countryName", country.getNames().get("zh-CN"));
                    imp.put("isoCode", country.getIsoCode());
                    imp.put("countryIp", imp.get("ip"));
                    imp.put("code", continent.getCode());
                    countryList.add(imp);
                } catch (IOException e) {
                    e.printStackTrace();
                } catch (GeoIp2Exception e) {
                    e.printStackTrace();
                }
            });
            //打印局域网IP
            System.out.println("innerAllIpList: " + innerAllIpList.size());
            System.out.println("publicIp: " + publicIp.size());
            System.out.println("===================打印需要分配给采集服务器IP地理位置=====================");
            //采集服务注册的IP,往这里分配交换机IP
            List<CountryModel> nodelist = nodelists;
            List<String> list_ip = redisclient.smembers("collet:node", 0);
            //删除洛杉机节点,不分配任务,只作备选节点
            list_ip.remove(laxIp);
    
            //中国的IP记录下来
            List<String> cn_ip_list = cn_ip_lists;
            if (null == list_ip) {
                return;
            }
            list_ip.stream().filter(s -> !StringUtils.isBlank(s)).forEach(nodeip -> {
                try {
                    InetAddress ipAddress = InetAddress.getByName(nodeip);
                    CityResponse response = reader.city(ipAddress);
                    Continent continent = response.getContinent();
    
                    Country country = response.getCountry();
                    if (null != response) {
                        CountryModel model = new CountryModel();
                        model.setName(country.getNames().get("zh-CN"));
                        model.setIsoCode(country.getIsoCode());
                        model.setCountryIp(nodeip);
                        model.setCode(continent.getCode());
                        nodelist.add(model);
                        if (country.getIsoCode().equals("CN")) {
                            cn_ip_list.add(nodeip);
                        }
                        System.out.println(model.getName() + ", EN: " + model.getIsoCode() + " IP: " + model.getCountryIp());
                    } else {
                        System.out.println("************************* response is null: " + response + " IP: " + nodeip);
                    }
                } catch (IOException e) {
                    e.printStackTrace();
                } catch (GeoIp2Exception e) {
                    e.printStackTrace();
                }
            });
        }
    
        //分配给采集服务器的IP
        public Map<String, List<Map<String, Object>>> nodeIPtask(List<Map<String, Object>> publicIp, List<Map<String, Object>> innerIp,
                                                                 List<CountryModel> nodelist, List<String> cn_ip_list) {
    
            //处理 没有区域交换机的IP数据,所有日本,台湾等IP
            List<Map<String, Object>> publicTaskList = new ArrayList<>();
    
            Map<String, List<Map<String, Object>>> listAllMap = new HashMap<String, List<Map<String, Object>>>();
            List<CountryModel> strlist = new ArrayList<>();
    
            //中国一个LIST  国外一个LIST,区分开来
            nodelist.stream().forEach(countryModel -> {
    
                listAllMap.put(countryModel.getCountryIp(), new ArrayList<>());
    
                //单独给中国一个LIST
                List<Map<String, Object>> publicTaskCnmap = new ArrayList<>();
                // 除了中国之外的IP节点,并且有服务器区域的
                List<Map<String, Object>> publicTaskAll = new ArrayList<>();
    
                strlist.add(countryModel);
                for (int s = 0; s < publicIp.size(); s++) {
                    if (countryModel.getIsoCode().equals(publicIp.get(s).get("isoCode")) && countryModel.getIsoCode().equals("CN")) {
                        publicTaskCnmap.add(publicIp.get(s));
                    } else if (countryModel.getIsoCode().equals(publicIp.get(s).get("isoCode"))) {
                        publicTaskAll.add(publicIp.get(s));
                    }
                }
                if (publicTaskCnmap.size() > 0) {
                    listAllMap.put(countryModel.getCountryIp(), publicTaskCnmap);
                }
                if (publicTaskAll.size() > 0) {
                    listAllMap.put(countryModel.getCountryIp(), publicTaskAll);
                }
            });
    
            //采集服务器重复的IP记录,再分配,  isocode相同,但是IP不相同,说明不是同一个节点, 多个服务的时候,old_ip和oldNodeip有重复,因为后面用KEY处理,重复的会覆盖
            List<String> old_ip = new ArrayList<>();
            Map<String, List<String>> old_map = new HashMap();
            // 是否同一国家
            nodelist.stream().forEach(same -> {
                //同一个国家两个节点以上,分配任务,多个节点轮询分配
                if (!old_map.containsKey(same.getIsoCode())) {
                    old_map.put(same.getIsoCode(), new ArrayList<>());
                }
                nodelist.stream().forEach(nodeSame -> {
                    if (same.getIsoCode().equals(nodeSame.getIsoCode()) && !same.getCountryIp().equals(nodeSame.getCountryIp())) {
                        old_ip.add(nodeSame.getCountryIp());
                        old_map.get(same.getIsoCode()).add(nodeSame.getCountryIp());
                    }
                });
            });
    
            //相同国家的的IP,重新再分配,先删除重复的IP KEY健值
            Map<String, List<Map<String, Object>>> sameListIsocode = new HashMap<>();
            // 用重复的ID去 删除KEY值
            listAllMap.forEach((s, maps) -> {
                old_ip.stream().forEach(s1 -> {
                    if (s.equals(s1)) {
                        sameListIsocode.put(s, maps);
                        listAllMap.put(s, new ArrayList<>());
                    }
                });
            });
            //平均分配两个,一个区域CN 下面有多个IP,得到一个LIST值, 轮询分到重复的IP上
            old_map.forEach((code, maps) -> {
                //有两个节点相同的国家
                if (maps.size() > 0) {
                    List<Map<String, Object>> ziNode = new ArrayList<>();
                    ziNode = sameListIsocode.get(maps.get(0));
                    int f = 0;
                    for (int j = 0; j < ziNode.size(); j++) {
                        if (f >= maps.size()) {
                            f = 0;
                        }
                        listAllMap.get(maps.get(f)).add(ziNode.get(j));
                        f++;
                    }
                }
    
            });
    
            //======================================== 这是处理没有区域服务器IP的数据,比如日本台湾等
            publicIp.stream().forEach(smp -> {
                //如果采集服务器有这个IP区域,就不进行分配,标记
                boolean tagst = false;
                for (int s = 0; s < strlist.size(); s++) {
                    if (smp.get("isoCode").equals(strlist.get(s).getIsoCode())) {
                        tagst = true;
                    }
                }
                if (!tagst) {
                    publicTaskList.add(smp);
                }
            });
    
    // 按大洲重新分配 
    //没有洲的IP
            List<Map<String, Object>> no_zhou_list = new ArrayList<>();//
            //按国家分配后,再按大洲分配,有大洲的ip
            List<Map<String, Object>> have_zhou_list = new ArrayList<>();//
            publicTaskList.stream().forEach(smp -> {
                //如果采集服务器有这个IP区域,就不进行分配,标记
                boolean tagst = false;
                for (int s = 0; s < strlist.size(); s++) {
                    if (smp.get("code").equals(strlist.get(s).getCode())) {
                        tagst = true;
                    }
                }
                if (!tagst) {
                    no_zhou_list.add(smp);
                } else {
                    have_zhou_list.add(smp);
                }
            });
    
            //按大洲分配,亚洲,欧洲等
            Map<String, List<String>> zhouPlan = new HashMap<>();
            nodelist.stream().forEach(ms -> {
                if (!zhouPlan.containsKey(ms.getCode())) {
                    zhouPlan.put(ms.getCode(), new ArrayList<>());
                }
                zhouPlan.get(ms.getCode()).add(ms.getCountryIp());
            });
            //封装洲的MAP,先封装 后轮询分配
            Map<String, List<Map<String, Object>>> zall = new HashMap<>();
            zhouPlan.forEach((k, v) -> {
                if (!zall.containsKey(k)) {
                    zall.put(k, new ArrayList<>());
                }
                have_zhou_list.stream().forEach(zo -> {
                    if (k.equals(zo.get("code"))) {
                        zall.get(k).add(zo);
                    }
                });
                int zs = 0;
                List<Map<String, Object>> se = zall.get(k);
                for (int i = 0; i < se.size(); i++) {
                    if (zs >= v.size()) {
                        zs = 0;
                    }
                    listAllMap.get(v.get(zs)).add(se.get(i));
                    zs++;
                }
            });
            System.out.println("no_zhou_list-==========: " + no_zhou_list.size());
            //随机分配任务到各洲, 之前是轮询分配到国家
            int ns = 0;
            for (int y = 0; y < no_zhou_list.size(); y++) {
                if (ns >= nodelist.size()) {
                    ns = 0;
                }
                listAllMap.get(nodelist.get(ns).getCountryIp()).add(no_zhou_list.get(y));
                ns++;
            }
    
    /*    
            int ns = 0;
            for (int y = 0; y < publicTaskList.size(); y++) {
                if (ns >= nodelist.size()) {
                    ns = 0;
                }
                listAllMap.get(nodelist.get(ns).getCountryIp()).add(publicTaskList.get(y));
                ns++;
            }
            //内网分配到国外的采集服务器上,除了中国服务器,避免国内两台以上服务器采集, 顺序分配或轮询分配
            int x = 0;
            for (int t = 0; t < innerIp.size(); t++) {
                boolean tabCn = false;  //国内IP 不参与分配内网
                if (x >= strlist.size()) {
                    x = 0;
                }
                for (int e = 0; e < cn_ip_list.size(); e++) {
                    if (listAllMap.get(strlist.get(x).getCountryIp()).equals(cn_ip_list.get(e))) {
                        tabCn = true;
                    }
                }
                if (!tabCn) {
                    listAllMap.get(strlist.get(x).getCountryIp()).add(innerIp.get(t));
                }
                x++;
            }*/
    
            return listAllMap;
        }
    
        //GeoIP2-City 数据库文件,测试用于IP查询位置
        public static void getLiteIPinit() throws IOException, GeoIp2Exception {
            File database = getFileGeo();
            // this.getClass().getClassLoader().getResource("").getPath();  得到的是 ClassPath的绝对URI路径。
    
            // 创建 DatabaseReader对象
            DatabaseReader reader = new DatabaseReader.Builder(database).build();
    
            InetAddress ipAddress = InetAddress.getByName("18.8.6.22");
    
            CityResponse response = reader.city(ipAddress);
    
            Continent continent = response.getContinent();
            System.out.println(continent.getCode());            // 'US'
            System.out.println(continent.getName());               // 'United States'
            System.out.println(continent.getNames().get("zh-CN")); // '
    
            Country country = response.getCountry();
            System.out.println(country.getIsoCode());            // 'US'
            System.out.println(country.getName());               // 'United States'
            System.out.println(country.getNames().get("zh-CN")); // '美国'
    
            Subdivision subdivision = response.getMostSpecificSubdivision();
            System.out.println(subdivision.getName());    // 'Minnesota'
            System.out.println(subdivision.getIsoCode()); // 'MN'
    
            City city = response.getCity();
            System.out.println(city.getName()); // 'Minneapolis'
    
            Postal postal = response.getPostal();
            System.out.println(postal.getCode()); // '55455'
    
            Location location = response.getLocation();
            System.out.println(location.getLatitude());  // 44.9733
            System.out.println(location.getLongitude()); // -93.2323
    
        }
    
        // 判断IP是否是区域网
        public static boolean internalIp(String ip) {
    
            byte[] addr = new byte[0];
            try {
                //将ip字符串转为byte数组,注意:ip不可以是域名,否则会进行域名解析
                addr = InetAddress.getByName(ip).getAddress();
            } catch (UnknownHostException e) {
                e.printStackTrace();
            }
            final byte b0 = addr[0];
            final byte b1 = addr[1];
            //10.x.x.x/8
            final byte SECTION_1 = 0x0A;
            //172.16.x.x/12
            final byte SECTION_2 = (byte) 0xAC;
            final byte SECTION_3 = (byte) 0x10;
            final byte SECTION_4 = (byte) 0x1F;
            //192.168.x.x/16
            final byte SECTION_5 = (byte) 0xC0;
            final byte SECTION_6 = (byte) 0xA8;
            switch (b0) {
                case SECTION_1:
                    return true;
                case SECTION_2:
                    if (b1 >= SECTION_3 && b1 <= SECTION_4) {
                        return true;
                    }
                case SECTION_5:
                    switch (b1) {
                        case SECTION_6:
                            return true;
                    }
                default:
                    return false;
            }
        }
    
        // 第二种算法,平均分配IP到所有存活节点服务上
        public void avgIptask() throws IOException {
    
            //所有内网IP 不进行地址解析
            List<Map<String, Object>> innerAllIpList = new ArrayList<>();
    
            //所有公网IP,需要解析地区位置,分配采集任务
            List<Map<String, Object>> publicIp = new ArrayList<>();
    
            //采集服务注册的IP,往这里分配交换机IP
            List<CountryModel> nodelist = new ArrayList<>();
    
            //中国的IP,记录下来,跳过此IP去分配内网IP,用LIST防止有多个中国服务器
            List<String> cn_ip_list = new ArrayList();
    
            AllIplistTask(publicIp, innerAllIpList, nodelist, cn_ip_list);
    
            Map<String, List<Map<String, Object>>> listAllMap = new HashMap<String, List<Map<String, Object>>>();
            nodelist.stream().forEach(countryModel -> {
                listAllMap.put(countryModel.getCountryIp(), new ArrayList<>());
            });
    
            // 全并两个 IP 的LIST 数据
            List<Map<String, Object>> allIplist = new ArrayList<>();
            allIplist.addAll(publicIp);
            allIplist.addAll(innerAllIpList);
    
            int x = 0;
            int nodeSize = nodelist.size();
            for (int t = 0; t < allIplist.size(); t++) {
                boolean tabCn = false;  //国内IP 不参与分配内网
                if (x >= nodeSize) {
                    x = 0;
                }
                listAllMap.get(nodelist.get(x).getCountryIp()).add(allIplist.get(t));
                x++;
            }
            //把分配好任务的LIST保存到采集服务的IP上   放到redis 的节点上
            listAllMap.forEach((s, maps) -> {
                // JSONArray arraylist = new JSONArray(Collections.singletonList(maps));
                // System.out.println(arraylist.get(0));
                // redisclient.set(s, DataTransformation.parseListForMapsToJsonArrayStr(maps).toJSONString(), 0);
                System.out.println(DataTransformation.parseListForMapsToJsonArrayStr(maps).size());
            });
    
        }
    
        public static File getFileGeo() {
            // 容器里运行的时候,找不到文件路径  本地运行用下面路径
            File database = new File(Thread.currentThread().getContextClassLoader().getResource("GeoLite2-City.mmdb").getPath());
            //打包上线,用下面路径
            //File database = new File(System.getProperty("user.dir") + "/GeoLite2-City.mmdb");
            return database;
        }
    
        public static void main(String[] args) throws IOException {
            //这里因为是去读取本地的纯真库,所以有一个IO异常抛出
        /*    QQWry wry = new QQWry();
            NodeToolService nodeTool = new NodeToolService();
            List<Map<String, Object>> list = nodeTool.getSnmpAll();
            List<IPZone> listipzone = new ArrayList<>();
            list.stream().forEach(ipmap -> {
                listipzone.add(wry.findIP(ipmap.get("ip").toString()));
            });
            //  IPZone zone = wry.findIP("123.123.123.123");
            listipzone.stream().forEach(ipZone -> System.out.println(ipZone.getMainInfo()));
            //  System.out.println(zone.getMainInfo());
            // System.out.println(zone.getSubInfo());
    
            测试IP  加到LIST测试区域
            中国, EN: CN IP: 13
            南非, EN: ZA IP: 126.60
            美国, EN: US IP: 107.60
            德国, EN: DE IP: 107.40
            新加坡, EN: SG IP: 12.60
            俄罗斯, EN: RU IP: 128.60
            美国, EN: US IP: 107.49
    
            */
            try {
                getLiteIPinit();
            } catch (GeoIp2Exception e) {
                e.printStackTrace();
            }
            //180.168.61.243
            //boolean ipbyte = internalIp("127.0.0.1");
            //if (ipbyte) {
            //    System.out.println("10.68.1.243");
            //} else {
            //    System.out.println("判断局域网IP:" + "127.0.0.1");
            //}
        }
    
    }
    
    展开全文
  • 针对多机器人系统中机器人决策之间的相互依存性, 引入博弈论的思想分析了多机器人系统的任务分配问题, 提出了一种基于博弈论的多机器人系统任务分配算法(GT-MRTA)。实验结果表明, 算法复杂度较低, 计算量较小, 鲁棒...
  • 作为社会网络研究的核心技术之一,对于感知参与者的位置和轨迹不确定性的问题造成群智感知数据实时性较差,为此,提出了一种基于空间任务分配的移动群智任务分配算法。该算法采用动态和自适应的数据驱动方案获取最优...
  • 尽管同步模式协同算法允许团队在许多通用网络拓扑中达成一致状态感知并执行任务分配,但收敛到一致状态感知需要花费大量时间,传输大量数据。在低带宽环境中这会导致严重的潜在问题,增加求解任务方案时间。分析了...
  • 12.29 任务分配算法 下面介绍如何将合适的工作分配给正在请求任务的工人 W。采用的思路是首先对每一个任务,都考虑如果将 W 中的某些工人安排给它,它的准确率会有多少提升;然后选择为每个工人选择最优的 h个任务,...

    12.29 任务分配算法

    下面介绍如何将合适的工作分配给正在请求任务的工人 W。采用的思路是首先对每一个任务,都考虑如果将 W 中的某些工人安排给它,它的准确率会有多少提升;然后选择为每个工人选择最优的 h个任务,以最大化地提升准确率。

    准确率估算 : 在推断模型中,P(z t,k ) 被用来推断 l t,k 的真实结果。如果 l t,k 的真实结果是 1,那么推断的准确率就是 P(z t,k =1);如果真实结果是 0,那么推断的准确率就是 P(z t,k =0)。因此,需就真实结果是 1 或者 0 两种情况考虑准确率。但两者相似,为简化描述,统一由 Acc t,k 来表示准确率。在任务分配过程中,如果任务 t 被安排给一组新的工人集合,记为 W(t) W,由于 t 的答案改变了,Acc t,k 就会产生改变。记 Acc t,k (W(t)) 为考虑加入工人 W(t)的答案后的改变的 t 准确率。 通过推断模型的公式演算,可以证明 W(t) 中任务被安排给工人的不同顺序对准确率不会产生影响,并且 Acc t,k (W(t)) 可以在线性时间内计算获得。

    最优任务分配 : 对正在请求任务的工人集合 W,目标是寻找一个分配方法来最大化期望准确率的提升。即寻找分配以最大化 ∆Acc t,k (W(t))。可以证明这一最大化问题是 NP-hard 的,由此,采用贪心算法来进行任务分配。贪心的过程是每次选择能够最大化期望准确率的〈工人,任务〉,将任务安排给该工人,不停选择直到为每个工人分配 h 个任务。

    展开全文
  • 针对武器装备快速扩散制造环境下的任务分配问题,提出了一种基于最小费用网络流的任务分配方法。本方法以完成任务的时间及费用最少为目标,首先计算出各个零件的最大产量,其次根据零件最大产量计算出产品的最大产量...
  • 夜光精讲 Opentcs 三大算法(二)任务分配算法

    千次阅读 热门讨论 2019-05-17 14:40:15
    不同于订单类型的任务,自启动任务通过实时检测AGV电量状态和任务池完成状态而自动发起的任务,因此无需由控制中心指派AGV,任务产生时己绑定了相应的车辆。 1.充电任务: AGV在运行过程中会产生大量...

    夜光序言:

     

    原谅不是无视,而是容纳。一个意味含蓄的笑容。只能是各自的担当。

     

     

     

     

     

     

    正文:

    白启动任务

    自启动任务分为充电任务和停靠任务。不同于订单类型的任务,自启动任务通过实时检测AGV电量状态和任务池完成状态而自动发起的任务,因此无需由控制中心指派AGV,任务产生时己绑定了相应的车辆。


    1.充电任务:


    AGV在运行过程中会产生大量的电量消耗,因此需能够及时充电以保证后续的正常运转。我们设计充电时电量剩余指标:critical   level, good  level 和perfect  level。

    三段式电量百分比设计充分提高系统中车辆的利用率。

     

    通常情况下,车辆处于perfect  level或good  level状态。当电池电量低于critical  level百分比时,AGV进入电量严重不足状态,车体客户端通过调用getRechargeO peration函数发出充电请求信号通知控制中心、控制中心、指派充电任务给此AGV,同时指定空闲的充电站点。此间AGV接受任何订单,AGV将当前子任务执行完毕后执行充电任务,其他尚未执行的任务进行重新分配。


    当AGV进行充电将电量回升至高于good  level时,可以接受订单,若无订单,则继续充电。
    当AGV充电完成100%时,结束充电任务,若无订单任务的指派,能自启动停靠任务进行停泊,让出空闲的充电站点。



    2.停靠任务:当AGV当前完成所有任务且无其他新的任务,就近停泊,可以节省电量消耗的同时,为地图减少一个动态障碍点,使得系统的行驶夏加通畅。


    (1)调用isParkPosWon(Point*a)函数:判断当前点是否可停靠;
    (2)调用getParkPoints(car,points)函数:收集当前可W停靠的点,排除臣经被其他vehicle占用的或被其他小车订单预定的点(状态数为2),即小车不会停靠到其他车辆未来将要经过的路径上。
    (3)从(2)的点中调用getNearestPoint(vehicle,points)函数:找到当前离小车最近的未被占用的目标停靠点;
     


    2 . 任务执行状态


    任务执行状态枚举类为enumTASK_STATUS{枚举值表}


    展开全文
  • 一种基于平均思想的任务分配算法

    万次阅读 多人点赞 2017-08-28 19:37:52
    假设现在有20个任务需要分配给员工去做,但是每个员工手头上还有未完成的任务,且未完成任务数不同。

            假设现在有n个任务需要分配给m个审核员去完成,但是每个审核员手头上还有未完成的任务,且未完成的任务数不同。那么如何均匀的把这些任务分配给各个审核员呢?这里我提出了一种基于平均思想的任务分配算法(我称之为标杆算法)。

            算法的主要思想是:首先找出所有审核员中手头未完成任务数最大的审核员,然后其它审核员以该审核员的未完成任务数为标杆,计算自己可容纳的任务数,最后所有审核员可容纳的任务数之和即为总的可容纳任务数(ava_task)。

            这里有两种情况,第一种情况是:总的可容纳任务数小于或等于n个待分配的任务数,此时所有审核员以最大未完成任务数(max_task)为标杆,接收待分配的任务。如果刚好分配完,那么算法结束;如果还有剩下的任务未分配,那将剩下的任务抽取m个任务分配给每一个审核员,依次类推,直到剩下的未分配任务数小于m为止,然后再将这小于m的任务随机分配给相应数量的审核员。第二种情况是:总的可容纳任务数大于n个待分配的任务数,此时降低一个单位的标杆(max_task-1),然后循环计算可容纳的任务数,直到退出循环(循环终止条件为:ava_task - task_num <= lower_List.size(),lower_List.size()表示的是低于当前标杆的审核员数)。

            接下来,我们将通过一个简单的例子来说明算法的流程,由于第一种情况比较简单,因此,该例子是基于第二种情况的,,如图1所示。


    图1

            假设有20个任务需要分配给8个审核员(对应8个条形图,实线条形图里的数字代表该审核员手头未完成的任务数)。首先找出这8个审核员中未完成任务数的最大值max_task=7,然后各审核员以max_task为标杆计算各自可容纳的任务数(对应虚线条形图里的数字),总的可容纳任务数为所有审核员可容纳的任务数之和,即ava_task=6+3+4+2+5+0+5+6=31,由图1可知,lower_List.size()=7,由于31-20>7,因此可降低一个单位的标杆,即max_task=max_task-1=6,如图2所示。


             那么,ava_task=5+2+3+1+4+0+4+5=24,lower_List.size()=7,由于24-20<7,因此循环终止。由于可容纳的任务数仍然大于待分配的任务数,因此需要再降低一个单位的标杆(一定要考虑这种情况),max_task=max_task-1=5,此时ava_task=4+1+2+0+3+0+3+4=17,lower_List.size()=6,剩余待分配任务数为20-17=3,然后将这3个任务随机分配给低于当前标杆的6个审核员中的3个,每个审核员分配一个。当然算法中还考虑了很多种情况,具体请参见如下代码。由于任务一般按审核员ID来分配,且ID一般为字符串。为了存储方便,我定义了一个二维字符串类型的数组rev_task[i][j]来存储数据,i表示第i个审核员,rev_task[i][0]存放的是第i个审核员的ID,rev_task[i][1]存放的是第i个审核员当前未完成的任务数,rev_task[i][2]存放的是第i个审核员应当被分配的任务数。

    算法工具类-AlgorithmUtils.java

    package com.yushen.allocationAlgorithm;
    
    import java.util.ArrayList;
    import java.util.Date;
    import java.util.List;
    import java.util.Random;
    
    public class AlgorithmUtils {
        public static void taskAllocation(int task_num, int rev_num, String[][] rev_task) {
    
            Random rd = new Random();
            List<Integer> rdList = new ArrayList<>();
            int temp;
    
            //获得审核人员中的最大未完成任务数
            int max_task = Integer.parseInt(rev_task[0][1]);
            for(int i = 1; i < rev_num; i++){
                if(max_task < Integer.parseInt(rev_task[i][1]))
                    max_task = Integer.parseInt(rev_task[i][1]);
            }
    
            //以最大待审核任务数为标杆,判断第一轮可容纳的任务数
            int ava_task = 0;
            List<Integer> lower_List = new ArrayList<>();
            for(int i=0;i<rev_num;i++){
                if((max_task-Integer.parseInt(rev_task[i][1])) > 0){
                    ava_task += (max_task-Integer.parseInt(rev_task[i][1]));
                    lower_List.add(i);
                }
            }
    
            int task_rest;
            int task_avg;
            //第一种情况:第一轮可容纳的任务数小于待分配的任务数
            if(ava_task - task_num <= 0) {
                for(int i = 0; i < rev_num; i++) {
                    rev_task[i][2] = String.valueOf(max_task-Integer.parseInt(rev_task[i][1]));
                }
                task_rest = task_num-ava_task;
                task_avg = task_rest/rev_num;
                if(task_rest != 0) {
                    while(task_avg > 0) {
                        for(int i = 0; i < rev_num; i++) {
                            rev_task[i][2] = String.valueOf(Integer.parseInt(rev_task[i][2])+task_avg);
                        }
                        task_rest -= rev_num*task_avg;
                        task_avg = task_rest/rev_num;
                    }
                    rdList.removeAll(rdList);
                    while(rdList.size() < (task_rest+1)){
                        temp = rd.nextInt(rev_num);
                        if(!rdList.contains(temp)){
                            rdList.add(temp);
                        }
                    }
                    for(int i = 0; i < task_rest; i++) {
                        rev_task[rdList.get(i)][2] = String.valueOf(Integer.parseInt(rev_task[rdList.get(i)][2])+1);
                    }
                }
            }else {//第二种情况:第一轮可容纳的任务数大于待分配的任务数,此时降低一个单位的标杆(max_task-1),然后循环计算可容纳的任务数,直到退出循环
                while(ava_task - task_num > lower_List.size()) {
                    max_task--;
                    ava_task = 0;
                    lower_List.removeAll(lower_List);
                    for(int i=0;i<rev_num;i++){
                        rev_task[i][2] = "0";
                        if((max_task-Integer.parseInt(rev_task[i][1])) > 0){
                            rev_task[i][2] = String.valueOf(max_task-Integer.parseInt(rev_task[i][1]));
                            ava_task += Integer.parseInt(rev_task[i][2]);
                            lower_List.add(i);
                        }
                    }
                }
                if(ava_task - task_num > 0) {//如果可容纳的任务数大于待分配的任务数,那么需要再再降低一个单位的标杆
                    max_task--;
                    ava_task = 0;
                    lower_List.removeAll(lower_List);
                    for(int i=0;i<rev_num;i++){
                        if((max_task-Integer.parseInt(rev_task[i][1])) >= 0){
                            rev_task[i][2] = String.valueOf(max_task-Integer.parseInt(rev_task[i][1]));
                            ava_task += Integer.parseInt(rev_task[i][2]);
                            lower_List.add(i);
                        }
                    }
                    task_rest = task_num - ava_task;
                    rdList.removeAll(rdList);
                    while(rdList.size() < (task_rest+1)){
                        temp = rd.nextInt(rev_num);
                        if((!rdList.contains(temp))&&(lower_List.contains(temp))){
                            rdList.add(temp);
                        }
                    }
                    for(int i = 0; i < task_rest; i++) {
                        rev_task[rdList.get(i)][2] = String.valueOf(Integer.parseInt(rev_task[rdList.get(i)][2])+1);
                    }
                }else {
                    task_rest = task_num-ava_task;
                    if(task_rest != 0) {
                        rdList.removeAll(rdList);
                        while(rdList.size() < (task_rest+1)){
                            temp = rd.nextInt(rev_num);
                            if((!rdList.contains(temp))&&(lower_List.contains(temp))){
                                rdList.add(temp);
                            }
                        }
                        for(int i = 0; i < task_rest; i++) {
                            rev_task[rdList.get(i)][2] = String.valueOf(Integer.parseInt(rev_task[rdList.get(i)][2])+1);
                        }
                    }
                }
            }
    
            //记录被分配的任务数
            for(int i=0;i<rev_num;i++){
                rev_task[i][1] = String.valueOf(Integer.parseInt(rev_task[i][1])+Integer.parseInt(rev_task[i][2]));
            }
        }
    }
    算法测试类-TestAlgorithm.java
    package com.yushen.allocationAlgorithm;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Random;
    import java.util.Scanner;
    
    public class TestAlgorithm {
    
    	public static void main(String[] args) {
    		
    	    Scanner sc=new Scanner(System.in);
    	    System.out.println("请输入任务数:");
    	    int task_num = sc.nextInt();
    	    System.out.println("请输入审核人员的当前未完成任务数组,整数数字输入时用英文逗号隔开:");
    	    String inputString=sc.next().toString();
    	    String stringArray[]=inputString.split(",");
    	    
    	    int rev_num = stringArray.length;//审核人员总数
    	    String[][] rev_task =new String[rev_num][3];
    	    Random rd = new Random();
    	    List<Integer> rdList = new ArrayList<>();
    	    rdList.removeAll(rdList);
    	    int temp;
    	    while(rdList.size() < (rev_num+1)){
    	    	temp = rd.nextInt(100);
                    if(!rdList.contains(temp)){
    		    rdList.add(temp);
                    }  
                }
    	    
    	    System.out.println("算法前的任务分配:");
    	    for(int i=0;i<rev_num;i++){
    	    	rev_task[i][0] = String.valueOf(rdList.get(i) + 1);
    	    	rev_task[i][1]= stringArray[i];
    	    	rev_task[i][2] = "0";
    	    	System.out.print(rev_task[i][0]+","+rev_task[i][1]+" ");
    	    }
    	    System.out.println();
    	     
                AlgorithmUtils.taskAllocation(task_num, rev_num, rev_task);//调用算法工具类
                System.out.println("算法后的任务分配:");    
                for(int i=0;i<rev_num;i++){    
                    System.out.print(rev_task[i][0]+","+rev_task[i][1]+" ");  
                } 
            }
    }
    运行结果:
    请输入任务数:
    20
    请输入审核人员的当前未完成任务数组,整数数字输入时用英文逗号隔开:
    1,4,3,5,2,7,2,1
    算法前的任务分配:
    72,1 63,4 73,3 49,5 74,2 43,7 100,2 20,1 
    算法后的任务分配:
    72,5 63,5 73,5 49,6 74,5 43,7 100,6 20,6

    由运行结果可知,20个任务均衡的分配给了每个审核人员,达到了平均分配的目的!
    本人才疏学浅,如有疏漏,请各位大虾不吝赐教!

    展开全文
  • 夜光分析可知,任务优先级顺序为:充电任务(电量低于criticallevel时)>充电任务(电量低于good level时)>订单任务>充电任务(电量高于good level时)>停靠任务。 因此停靠...
  • 夜光序言: 青年眼眸微闭,双手放于脑后,自言自语道: 享受悠闲生活当然比享受奢侈生活便宜得...此时出库任务的第⑤段子任务取消回退,等到AGV运载小车依次至多个操作台完成所有请求后,再将货架送回至存货...
  • 一个简单的订单出库任务的流程图: (1)接收订单:由ERP或WEB端添加输入新的订单并发送给控制中心 (2)查询订单货物信息:CCS控制中心向WMS申请查询货物存储库存信息和位置; (3)补充订单...
  • :多机器人任务分配(MRTA) 由欧洲委员会Interreg France-Channel-England Program资助的旨在改进涉及自主协作机器人(CoRoT)的灵活,响应快速的制造系统的设计。 我的MRTA项目是CoRot的一部分,是在实验室,...
  • 交流:资源分配算法任务卸载算法 本人在读硕士,在资源分配方面有一定的实战经验与算法能力(MOPSO、SPEAII等),主打编程(Matlab)与论文,若您有需求,望能够与各位交流,QQ:583746893(微信同号)。 ...
  • 任务分配问题算法

    千次阅读 2020-04-15 15:28:47
    任务分配问题算法代码简化至34行 问题:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。 源代码: import ...
  • 在问题模型中设计考虑资源损耗的编组资源能力更新机制, 提出用于求解该模型的动态列表规划和量子遗传算法的混合任务分配算法, 使用动态列表规划选择处理的任务, 利用量子遗传算法为选定任务分配最合适编组....
  • 该文章能够提供一个任务分配的框架,基于该框架实现任务负载均衡,里面的算法思想较为适用。
  • 基于改进的PSO算法求解任务分配模型,研究了求解问题与粒子的映射以及采用TOPSIS计算粒子位置适应度的方法,进而设计了一种基于改进PSO算法的任务分配算法。通过应用实例及仿真实验,证明了改进的PSO算法应用于任务...
  • OTAP:基于预测的机会群智感知多任务在线分配算法
  • 针对0-1任务规划模型存在维数灾维的问题,提出了一种基于改进差分进化算法的整数任务分配算法。将任务分配的0-1规划模型转化整数规划模型,不仅大幅降低了优化变量的维数,还减小了整式约束条件;将差分进化算法常用...
  • 一种基于最大流的分布式存储系统中查询任务 最优分配算法
  • 提出了一种在WDM网络中基于优先级的多任务波长路由分配算法。算法设计旨在提高光网络资源的利用率、降低网络请求阻塞率。分析了任务请求的路由类型以及负载容量对请求优先级划分的影响方式,给出了网络请求优先级...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,088
精华内容 835
关键字:

任务分配算法