PHP 分配问题，怎么实现最优分配呢？

Question

1、把人员分成 20组
2、5个实验台
1 实验台需要2小时
2 实验台需要 3小时
3 实验台需要 4小时
4 实验台需要 1小时
5 实验台需要 5小时
3、每个实验台 每个小组必须都做一遍。
4、一天做不完，可以推到第二天，第二天完不成可以再推 等等
5、第一小组占用实验台 ，第二小组可以选择别的实验台，第三小组等等类推
6、假设 2017-11-1日开始

假如上午8点开始 12点结束
假如下午13点开始 18点结束

结果模拟
第一小组 第一天 第一小组第二天
1实验台 8点-10点 3实验台
4实验台 10点-11点 4实验台
5实验台 13点-18点
第二小组 第二小组第二天
2实验台 8-11 1实验
4实验台 11-12 5实验
3实验台 13-17

我实现了分配，但是存在问题，不能达到最优分配

代码如下，

class Demo extends Basic
{
    public $days = array();
    public $content = array();
    public $run_date = '2017-10-01 08:00';
    public $run_date_n = '2017-10-01 13:00';
    public $run_group = 1;
    public $run_room = array();
    public $run_content = array();
    public $run_noon_m = '240';
    public $run_after_noon_m = '300';
    public $run_ext_content = null;

    function __construct()
    {
        parent::__construct();
    }

    function combination()
    {

        $this->content = array(
            24 => '180',
            25 => '120',
            26 => '240',
            27 => '60',
            28 => '300'
        );

//        // 第一组
        $this->run_content = $this->content;
        $this->run_ext_content = null;

        $this->_get_days();

        var_dump($this->days);

        $this->days = array();
    }

    private function _get_days()
    {
        $day_list = $this->_get_day();

        $other = $this->_check_ext_content();

        $this->days[] = $day_list;

        if (!empty($other)) {
            $this->run_date = date('Y-m-d H:i', (strtotime($this->run_date) + 86400));
            $this->run_date_n = date('Y-m-d H:i', (strtotime($this->run_date_n) + 86400));

            $this->run_content = $other;
            return $this->_get_days();
        }

        if (!empty($this->run_content)) {
            return $this->_get_days();
        }
    }

    private function _get_day()
    {

        $this->_check_content();
        $_noon = $this->_get_most_noon();
        $this->_check_content();
        $_after_noon = $this->_get_most_afternoon();

        return array(
            'date_noon' => $this->run_date,
            'date_afternoon' => $this->run_date_n,
            'noon' => $_noon,
            'after_noon' => $_after_noon
        );
    }

    private function _get_most_noon()
    {
        if (!empty($this->run_content)) {
            $list = $this->_get_combination($this->run_content, $this->run_noon_m);

            if (!empty($list)) {
                $frist = each($list);

                // 验证最优安排时间是否被占用
                if (!empty($this->run_room)) {

                    $keys = explode('|', $frist['key']);

                    foreach ($keys as $room) {
                        if (!empty($this->run_room[$room])) {
                            $_end = (strtotime($this->run_date) + $this->content[$room] * 60);

                            $run_noon = $this->run_date . '|' . date('Y-m-d H:i', $_end);
                            if (in_array($run_noon, $this->run_room[$room]) === true) {
                                unset($this->run_content[$room]);
                                return $this->_get_most_noon();
                            }
                        }
                    }

                    $this->run_ext_content .= $this->run_ext_content === null ? $frist['key'] : '|' . $frist['key'];
                    return $frist['key'];
                } else {
                    $this->run_ext_content .= $this->run_ext_content === null ? $frist['key'] : '|' . $frist['key'];
                    return $frist['key'];
                }
            }
        }
    }

    private function _get_most_afternoon()
    {
        if (!empty($this->run_content)) {
            $list = $this->_get_combination($this->run_content, $this->run_after_noon_m);

            if (!empty($list)) {
                $frist = each($list);

                // 验证最优安排时间是否被占用
                if (!empty($this->run_room)) {

                    $keys = explode('|', $frist['key']);

                    foreach ($keys as $room) {
                        if (!empty($this->run_room[$room])) {
                            $_end = (strtotime($this->run_date_n) + $this->content[$room] * 60);
                            $run_afternoon = $this->run_date_n . '|' . date('Y-m-d H:i', $_end);
                            if (in_array($run_afternoon, $this->run_room[$room]) === true) {
                                unset($this->run_content[$room]);
                                return $this->_get_most_afternoon();
                            }
                        }
                    }
                    $this->run_ext_content .= $this->run_ext_content === null ? $frist['key'] : '|' . $frist['key'];
                    return $frist['key'];
                } else {
                    $this->run_ext_content .= $this->run_ext_content === null ? $frist['key'] : '|' . $frist['key'];
                    return $frist['key'];
                }
            }
        }
    }

    private function _get_combination($lists, $like)
    {
        $_combination = array();
        if (!empty($lists) && !empty($like)) {
            $combination_list = \Math\Combinatorics\Combination::get($lists);
            foreach ($combination_list as $item) {
                $_sum_time = 0;
                $_c_ids = null;
                foreach ($item as $_c_id => $_c_tiem) {
                    $_sum_time += $_c_tiem;
                    $_c_ids .= $_c_ids === null ? $_c_id : '|' . $_c_id;
                }

                $_combination[$_c_ids] = $like - $_sum_time;
            }

            foreach ($_combination as $key => $item) {
                if ($item < 0) {
                    unset($_combination[$key]);
                }
            }

            asort($_combination);

            return $_combination;
        }
        return $_combination;
    }

    private function _check_ext_content()
    {
        $used = explode('|', $this->run_ext_content);
        $content = $this->content;
        foreach ($used as $_key) {
            unset($content[$_key]);
        }
        return $content;
    }

    private function _check_content()
    {
        if (!empty($this->run_ext_content)) {
            $used = explode('|', $this->run_ext_content);

            foreach ($used as $_key) {
                unset($this->run_content[$_key]);
            }
        }
        return false;
    }

}

哪位大神有思路，望指点一二。

Answer 1

可以这样理解吗，工作台=worker 人=job，工作台需要的时间就是worker完成任务的时间，job放入队列，worker争抢任务就是了