New Lower Bounds for The Best-Case Schedule in Groups of Permutable Operations. Issue 3 (2015)

• Record Type: Journal Article
• Authors: Yahouni, Z.; Mebarki, N.; Sari, Z.
• Is Part Of: IFAC-PapersOnLine. Volume 48:Issue 3(2015)
• Page Start: 1134
• Page End: 1139
• Publication Date: 2015
• Subjects: Groups of permutable operations -- Best-case -- Scheduling -- Uncertainty -- Job Shop -- Lower bounds; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2015.06.236
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: Groups of permutable operations is a well-known robust scheduling method that represents a particular set of schedules to be used in a real-time human-machine decision system where the aim is to absorbe uncertainties. This method guarantees a minimal quality corresponding to the worst-case. The best-case quality is also of interest; associated with the worst-case, it will provide a range of all possible qualities of the final schedule. The best-case quality is an NP-hard problem that can be solved optimally using an exact method. The performance of this exact method relies on the accuracy of its lower bounds. In this paper, we propose new improved lower bounds for the best-case quality of the groups of permutable operations. These lower bounds can either be used in an exact method to seek for the optimal best solution or can be used in a real-time human-machine decision system. The experiments made on very well-known job shop instances, using the makespan objective, exhibit very good performances.