5

我与您联系是为了了解“如何将流水车间调度问题”转换为布尔可满足性。

我已经为 N*N Sudoku、N-queens 和 Class 调度问题做了这样的简化，但是我对如何将流水车间转换为 SAT 有一些问题。

SAT问题看起来像这样：

SAT问题的插图

目标是：使用不同的布尔变量，找到每个变量的做作，以使“句子”为真。（如果找到解决方案是可能的）。

我用遗传算法创建了自己的求解器，能够找到解决方案并证明什么时候没有解决方案。现在，我尝试解决不同的 NP 问题，比如 Flow Shop。

流水车间调度问题是车间或集团车间的一类调度问题，其中流控制应为每个作业和在一组机器上或使用其他资源的处理启用适当的排序 1,2,...,m遵守给定的处理订单。

尤其是希望以最少的空闲时间和最少的等待时间来维持处理任务的连续流。

流水车间调度是作业车间调度的一种特殊情况，其中对所有作业执行的所有操作都有严格的顺序。

流水车间调度也可以应用于生产设施，就像计算设计一样。

（http://en.wikipedia.org/wiki/Flow_shop_scheduling）

结果是一系列工作将通过每个研讨会，图形结果将如下所示：

流水车间的图形结果

因此，为了表示流水车间实例，在输入中我有这样的文件：

2 4
4 26 65 62 
63 83 57 9

这个文件意味着我有 2 个商店和 4 个工作，每台机器上每个工作的所有持续时间。

目标：找到最小化 C_max 的序列，如果您愿意，可以在最后一台机器上找到最后一个作业的结束日期。

我的 Flow-Shop 现在真的很简单，但我不知道如何将它们形式化以便创建一个 CNF 文件来执行我的 SAT 求解器。

如果你们中的一个人有一些想法：文章？一个想法的开始？

这个问题的下一部分：Flow/Job Shop to Boolean satisfiability [Polynomial-time reduction] part 2

4

3 回答 3

3

我会这样处理它：

对于每台机器上每个可能的时间开始的每个资源使用情况，您都有一个布尔变量（当然，这要求时间是有限且离散的，所以我假设整数）。

s_1_2_3因此，您会得到类似于从第二个 3 开始在机器 2 上使用资源 1 的含义的变量。

现在您可以根据这些变量制定各种条件。喜欢：

  • 每个资源一次只能在一台机器上使用
  • 每台机器一次只能处理一个资源
  • 机器步骤必须按顺序进行（机器 1 需要处理资源 x，然后机器 2 才能完成工作）

警告：即使是小问题，这也会产生大量的布尔表达式。

正如@gwilkins 提到的，您需要将优化问题转换为布尔问题。我会遵循他的方法：找到一个你愿意接受的最长时间，并解决这个时间限制（这实际上限制了变量的数量）。

您还可以从应该有解决方案的东西（例如添加的所有作业的时间）和自然下限（最长作业所需的时间）开始，然后通过拆分间隔找到最佳解决方案。

再一次：这可能会执行得很糟糕，但它应该提供正确的解决方案。

使用此变量制定的约束示例：

机器 1 必须先处理资源 x，然后机器 2 才能完成工作（假设工作的长度为 1）：

(S_x_1_1 and ! S_x_2_1) 
or (S_x_1_2 and ! S_x_2_1 and ! S_x_2_2) 
or (S_x_1_3 and ! S_x_2_1 and ! S_x_2_2 and ! S_x_2_3)
or ...
于 2015-04-08T10:15:01.827 回答
2

我正在使用 c#; if我通过以下语句处理该结果
：( EndTime = StartTime + Duration)

// This is for handling start of M1J4 that starts after end of M2J2
// Bt I think this is out of 'Flow Shop Working'
if (i > 1)
    if (M[m].jobs[i].StartTime < M[m + 1].jobs[i - 2].EndTime)
        M[m].jobs[i].StartTime = M[m + 1].jobs[i - 2].EndTime;

if (i > 0)
    if (M[m].jobs[i].StartTime < M[m + 1].jobs[i - 1].StartTime)
        M[m].jobs[i].StartTime = M[m + 1].jobs[i - 1].StartTime;
if (M[m + 1].jobs[i].StartTime < M[m].jobs[i].EndTime)
    M[m + 1].jobs[i].StartTime = M[m].jobs[i].EndTime;

我的控制台应用程序的代码是：

class job
{
    public int Id { get; set; }
    public int Duration { get; set; }
    public int StartTime { get; set; }
    public int EndTime { get { return this.StartTime + this.Duration; } } 

    public job(int _Id) { this.Id = _Id; }

    public override string ToString()
    {
        if (this.Duration == 1)
            return "|";
        string result = "[";
        for (int i = 0; i < this.Duration - 2; i++)
            result += "#";
        return result + "]";
    } 
}

class machine
{
    public int Id { get; set; }
    public List<job> jobs = new List<job>();
    public int C_Max { get { return this.jobs[jobs.Count - 1].EndTime; } }

    public machine(int _Id) { this.Id = _Id; }

    public job AddJob(int _Duration)
    {
        int newId = 1;
        if (newId < jobs.Count + 1)
            newId = jobs.Count + 1;
        jobs.Add(new job(newId));
        jobs[newId - 1].Duration = _Duration;
        if (newId == 1)
            jobs[newId - 1].StartTime = 0;
        else
            jobs[newId - 1].StartTime = jobs[newId - 2].EndTime;
        return jobs[newId - 1];
    }

    public void LagJobs(job fromJob, int lagDuration)
    {
        for (int i = fromJob.Id; i <= jobs.Count; i++)
            jobs[i].StartTime += lagDuration;
    }

    public void AddJobs(int[] _Durations)
    {
        for (int i = 0; i < _Durations.Length; i++)
            this.AddJob(_Durations[i]);
    }

    public override string ToString()
    {
        return this.ToString(false);
    }

    public string ToString(bool withMax)
    {
        string result = string.Empty;
        for (int i = 0; i < jobs.Count; i++)
        {
            while (jobs[i].StartTime > result.Length)
                result += " ";
            result += jobs[i].ToString();
        }
        result = this.Id.ToString() + ". " + result;
        if (withMax) 
            result += " : " + this.C_Max;
        return result;
    }
}

class Program
{
    static void Main(string[] args)
    {
        int machinesCount = 4;
        List<machine> machines = new List<machine>();
        for (int i = 0; i < machinesCount; i++)
        {
            machines.Add(new machine(i + 1));
        }
        machines[0].AddJobs(new int[] { 5, 5, 3, 6, 3 });
        machines[1].AddJobs(new int[] { 4, 4, 2, 4, 4 });
        machines[2].AddJobs(new int[] { 4, 4, 3, 4, 1 });
        machines[3].AddJobs(new int[] { 3, 6, 3, 2, 6 });
        handelMachines(machines);
        for (int i = 0; i < machinesCount; i++)
            Console.WriteLine(machines[i].ToString(true));
        Console.ReadKey();
    }

    static void handelMachines(List<machine> M)
    {
        if (M.Count == 2)
        {
            for (int i = 0; i < M[0].jobs.Count; i++)
            {
                if (i > 1)
                    if (M[0].jobs[i].StartTime < M[1].jobs[i - 2].EndTime)
                        M[0].jobs[i].StartTime = M[1].jobs[i - 2].EndTime;
                if (i > 0)
                    if (M[0].jobs[i].StartTime < M[1].jobs[i - 1].StartTime)
                        M[0].jobs[i].StartTime = M[1].jobs[i - 1].StartTime;
                if (M[1].jobs[i].StartTime < M[0].jobs[i].EndTime)
                    M[1].jobs[i].StartTime = M[0].jobs[i].EndTime;
            }
        }
        else
        {
            for (int i = 0; i < M.Count - 1; i++)
            {
                List<machine> N = new List<machine>();
                N.Add(M[i]);
                N.Add(M[i + 1]);
                handelMachines(N);
            }
        }
    }
}

结果是：
在此处输入图像描述

于 2015-04-08T09:24:54.643 回答
0

首先阅读此页面（作业车间调度）

问题是最短路径。对于最优的合理近似，忘记 SAT 表达式。尝试什么是显而易见的。如果您首先在 M1 上运行最短作业，则该作业已准备好使用 M2，而下一个最短作业正在使用 M1。
在这些问题中，每个人都忽略了等待状态的“幻像机”消耗时间。最大生产力相当于处于等待状态的最短时间。因此，每项工作都可以表示为一个二进制字符串，表示在生产或非生产任务中的时间。每组长度为 n 的字符串都可以用一个 n-SAT 表达式来表示。该表达式可以简化为 k-SAT 表达式，其中 2 < k < n，在多项式时间内。
剩下的就是“编码”问题；就像如何“编码”二进制字符串，以便解决 SAT 表达式产生你正在寻找的东西。

请参阅此（用于 3SAT 的三个完整的确定性多项式算法）来求解 SAT 表达式。

于 2019-12-27T18:02:21.023 回答