In this paper, the structure of infeasible solutions to Job Shop Scheduling Problem (JSSP) is quantitatively analyzed, and a necessary and sufficient condition of the deadlock for JSSP is also given. For a simple JSSP...In this paper, the structure of infeasible solutions to Job Shop Scheduling Problem (JSSP) is quantitatively analyzed, and a necessary and sufficient condition of the deadlock for JSSP is also given. For a simple JSSP with 2 machines and N jobs, a formula for calculating the infeasible solutions is proposed, which shows that the infeasible solution possesses the majority of search space and only those heuristic algorithms which do not produce infeasible solutions are valid.展开更多
基金Supported by The National Natural Science Foundation of China ( No.794 3 0 0 2 2 )
文摘In this paper, the structure of infeasible solutions to Job Shop Scheduling Problem (JSSP) is quantitatively analyzed, and a necessary and sufficient condition of the deadlock for JSSP is also given. For a simple JSSP with 2 machines and N jobs, a formula for calculating the infeasible solutions is proposed, which shows that the infeasible solution possesses the majority of search space and only those heuristic algorithms which do not produce infeasible solutions are valid.
