New lower bounds for solving a scheduling problem with resource collaboration. (January 2019)

• Record Type: Journal Article
• Authors: Ainbinder, Inessa; David Pinto, Gabriel; Rabinowitz, Gad
• Is Part Of: Computers & industrial engineering. Volume 127(2019)
• Page Start: 225
• Page End: 239
• Publication Date: 2019-01
• Subjects: Resource-sharing -- Scheduling -- Branch and bound -- Lower bound -- Model-driven decision support system; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.11.062
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Lower bounds (LBs) for the resource sharing and scheduling problem (RSSP) are proposed. Domination relations between the proposed LBs are provided. The LBs are implemented via a customized branch and bound (B&B) algorithm. Measures for comparing the LBs using 105 RSSP instances are defined. The results demonstrated a 70% runtime reduction compared to previously published methods and bounds. Web-based MDSS prototype for resource sharing and scheduling problem is proposed. Abstract: The collaboration of robots or other renewable resources for the efficient performance of complex operations is an essential part of modern industrial systems. Here we considered a key feature of the scheduling problem, namely, alternative modes by which to execute an operation. Every operation mode uses a specific set of collaborating resources to perform the operation. This structure allows the scheduling engineer to incorporate in each operation a set of activities using few resources, where each resource performs some of the activities during a portion of the operation's duration. As such, this setup allows the reuse of previously designed solution segments in a manner that conserves engineering efforts and reduces model size while retaining the flexibility conferred by the use of alternative modes. In this paper, we propose new lower bounds for improving the solution process efficiency and we demonstrate a model-driven decision support system for formulating and solving such scheduling problems. Two types of bounds are derived and analyzed, LP relaxation and parameters-based calculation. Both types consider partial solutions at the customized branch and bound solution tree. The dominance relations among the bounds are determined analytically, and the performances of the dominant bounds are compared empirically. The results demonstrate a 70% runtime reduction compared to previously published methods and bounds.