分支界限作业分配

分支界限算法解决作业分配问题 利用Ｃ＃语言实现

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Threading.Tasks;

namespace job
{
    class Program
    {

        int njob;                  //工人数量、作业数量
        int[] job;                 //分配给操作员的作业，用作最后的输出
        int[] cost;               //工人完成作业的时间
        [Serializable（）]           //标记为可序列化的
        struct Node
        {
            public int[] job;      //分配给操作员的作业
            public int time;       //当前搜索深度下已分配的作业所需的时间
            public int bound;      //当前节点的时间下界
        }
        static List list = new List（）;//存储节点的列表


        //结构体中含有数组，实现两个结构体赋值时是变量复制的形式
        public static T DeepClone（T obj）
        {
            using （var ms = new MemoryStream（））
            {
                var formatter = new BinaryFormatter（）;
                formatter.Serialize（ms obj）;
                ms.Position = 0;
                return （T）formatter.Deserialize（ms）;
            }
        }

        //对列表冒泡排序
        static void Sort（List list）
        {
            Node temp;
            for （int i = 0; i < list.Count - 1; i++）
            {
                for （int j = 1; j < list.Count - i; j++）
                {
                    if （list[j - 1].bound > list[j].bound）
                    {
                        temp = list[j];
                        list[j] = list[j - 1];
                        list[j - 1] = temp;
                    }
                }
            }
        }

     
        public static int JobAssign（int[] c int n int[] job）
        {
            Node xNode;
            Node yNode;
            int bound = 10000000;              
            int k = 0;                         //搜索深度
            xNode = new Node（）;
            xNode.job = new int[n];
            for （int i = 0; i < n; i++）
            {
                xNode.job[i] = -1;             //job[i]元素值为-1表示员工i还没有分配工作
            }
            xNode.time = xNode.bound = 0;
            while （k != n）                      
            {
                for （int i = 0; i < n; i++）    
                {
                    if （xNode.job[i] == -1）
                    {
                        yNode = new Node（）;
                        yNode = DeepClone（xNode）;
                        yNode.job[i] = k;     
                        yNode.time += c[i k]; 
                        yNode.bound = yNode.time;
                    
                        for （int j = k + 1; j < n; j++）
                        {
                            int min = 1000000;
                            for （int m = 0; m < n; m++）
                            {
                                if （yNode.job[m] == -1 && c[m j] <= min）
                                {
                                    min = c[m j];
                                }
         

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        187  2015-05-25 10:05  job\job\App.config

     文件       7168  2015-05-25 10:18  job\job\bin\Debug\job.exe

     文件        187  2015-05-25 10:05  job\job\bin\Debug\job.exe.config

     文件      15872  2015-05-25 10:18  job\job\bin\Debug\job.pdb

     文件      22984  2015-05-25 10:18  job\job\bin\Debug\job.vshost.exe

     文件        187  2015-05-25 10:05  job\job\bin\Debug\job.vshost.exe.config

     文件        490  2012-06-06 02:06  job\job\bin\Debug\job.vshost.exe.manifest

     文件       2547  2015-05-25 10:05  job\job\job.csproj

     文件       6466  2015-05-25 10:05  job\job\obj\Debug\DesignTimeResolveAssemblyReferencesInput.cache

     文件        257  2015-05-25 10:18  job\job\obj\Debug\job.csproj.FileListAbsolute.txt

     文件       7168  2015-05-25 10:18  job\job\obj\Debug\job.exe

     文件      15872  2015-05-25 10:18  job\job\obj\Debug\job.pdb

     文件          0  2015-05-25 10:05  job\job\obj\Debug\TemporaryGeneratedFile_036C0B5B-1481-4323-8D20-8F5ADCB23D92.cs

     文件          0  2015-05-25 10:05  job\job\obj\Debug\TemporaryGeneratedFile_5937a670-0e60-4077-877b-f7221da3dda1.cs

     文件          0  2015-05-25 10:05  job\job\obj\Debug\TemporaryGeneratedFile_E7A71F73-0F8D-4B9B-B56E-8E70B10BC5D3.cs

     文件       4783  2015-05-25 10:21  job\job\Program.cs

     文件       1326  2015-05-25 10:05  job\job\Properties\AssemblyInfo.cs

     文件        899  2015-05-25 10:05  job\job.sln

    ..A..H.     19968  2015-05-25 10:21  job\job.v11.suo

     目录          0  2015-05-25 10:05  job\job\obj\Debug\TempPE

     目录          0  2015-05-25 10:21  job\job\bin\Debug

     目录          0  2015-05-25 10:21  job\job\obj\Debug

     目录          0  2015-05-25 10:21  job\job\bin

     目录          0  2015-05-25 10:21  job\job\obj

     目录          0  2015-05-25 10:21  job\job\Properties

     目录          0  2015-05-25 10:21  job\job

     目录          0  2015-05-25 10:21  job

----------- ---------  ---------- -----  ----

               106361                    27



............此处省略0个文件信息