二机流水作业带不可用区间、工件可拒绝的调度问题

Two-Machine Flow-Shop Scheduling Problem with Unavailable Interval and Rejection

考虑了二机流水作业第一台机器带不可用区间、工件可拒绝的调度问题.所有的工件都是加工可中断的,即当某一工件在不可用区间出现之前开始加工但在机器不可用时并未加工完成,在不可用区间结束后可以接着加工.目标函数是最小化接受加工工件的最大完工时间与拒绝工件的惩罚之和.此问题是NP-难的.首先提出了一个动态规划的最优算法以求解小规模问题,并给出了数值计算实例.所提出的动态规划算法的运算时间随着问题的规模成指数增长,进而又提出了一个启发式算法,并证明了该启发式算法的最坏性能比是3.

A two-machine flow-shop scheduling problem with unavailability interval and rejection is considered.Interruption in workpiece process is allowed,namely if a workpiece begin to be processed before the unavailable interval appeared but has not been completed when the machine is unavailable,and it can be processed after the unavailability interval finished.The objective function is to minimize the sum of the maximum processing time of the wrokpiece that accept to be processed and penalty value of the workpiece that reject to be processed.It is an NP-hard problem.A dynamic programming algorithm is proposed for solving small scale problem optimally and a numerical example is given.Since the computation time of the dynamic programming algorithm increases exponentially with the scale of the problem increases,a heuristic algorithm is proposed and it is proved that the worst-case ratio of this heuristic algorithm is 3.