Production, Manufacturing and Logistics
An experimental analysis of solution performance in a resource sharing and scheduling problem

https://doi.org/10.1016/j.ejor.2003.12.020Get rights and content

Abstract

In this paper we study the performance of a branch and bound enumeration procedure in solving a comprehensive mixed-integer linear programming formulation of a resource-sharing and scheduling problem (RSSP). The formulation is monolithic and deterministic. Various independent factors of an RSSP generally influence the size of the problem. An experimental analysis is performed to examine how such factors influence performance. We found that the number of resources, the total number of modes allowed in the problem, and the average number of renewable resources used in the problem have significant influence on the computational time as well as other performance measures. In addition, some intermediate response variables are identified and additional insights regarding the influences of the independent factors on these variables are provided.

Introduction

Resource-sharing and scheduling is an important area of research that has significant practical implications in production planning because efficient and effective use of available production resources is vital for the ever increasing competitiveness to the manufacturing as well as service industry. In a batch-processing environment, production planning is concerned with the acquisition, utilization, and allocation of production resources over time to optimize certain criterion while satisfying constraints such as those imposed by resource capacity (Graves, 1982). Considerable research activities have been devoted to various production planning problems in the literature.

The general problem of resource-sharing and production planning is a very complex one. In addition to the size of the problem, it can be complicated by the environmental changes such as resource failures, delayed receipts of materials, changing demand (Mehra et al., 1995) as well as sequence-dependent setup times (Roslof et al., 2002). Thus the importance for a comprehensive yet implementable formulation and solution of the problem is clear as pointed out by Maxwell et al. (1983) that inadequate procedures for controlling and inventory and production could result in a loss of billions of dollars each year.

Mathematical programming is the common approach to modeling and solving the problem of resource-sharing and scheduling. Due to the nature of the problem, mathematical programming formulations are typically very large and complex. There are two distinct approaches to solving the general production planning and scheduling problem in the literature. The first approach, known as “hierarchical”, partitions the global problem into a hierarchy of subproblems (Hax and Meal, 1975; Bitran et al., 1981). The subproblems are solved sequentially with the solutions of upper hierarchy imposing constraints on subproblems of lower hierarchy. Bowers and Jarvis (1992) and Mehra et al. (1995) have presented recent applications of this approach to production planning in complex manufacturing systems. The main advantages of the hierarchical approach are summarized in Dempster et al. (1981) including reduction of complexity and adoption of random events, among others. However, the limitation of this approach is the system suboptimization caused by the decomposition and gradual solution process inherent in the hierarchical approach.

The second approach, termed “monolithic”, formulates the entire resource-sharing and scheduling problem as a large mixed-integer linear programming (see, for example, Manne, 1958; Lasdon and Terjung, 1971). The monolithic approach has the advantages of a well-defined mathematical programming model formulation from which global optimization is meaningful and possible. The major limitation of this approach lies in the need of solving a large complex mathematical programming problem. This disadvantage has caused many published work focusing only on highly simplistic or less-than-realistic assumptions regarding production systems. For example, a fixed (and hence singular) mode for an operation is popularly assumed, rather than multiple modes (i.e., alternative ways of executing an operation using different subsets of resources). In fact, none of the existing machine loading and tool allocation models (Co et al., 1990; Garetti et al., 1990; Kumar et al., 1990; Ram et al., 1990; Chen and Askin, 1990; Daniels and Sarin, 1989; Vinod and Solberg, 1985; Yao and Buzacott, 1986) allow simultaneously for: (1) multiple resources, (2) multiple modes, (3) continuous time, (4) independence of the time duration of each resource utilized by a given operation, (5) cooperation between resources (such as two robots synchronized to lift a heavy bucket together), (6) operations sharing resource(s) simultaneously, (7) explicit time delay for resource changeover, and (8) collision avoidance. The same limitation is observed for many production scheduling models (Kimemia and Gershwin, 1985; Chakravarty and Shtub, 1987; Schmitt et al., 1985) or for resource-constrained scheduling models (Davis, 1973; Talbot, 1982; Patterson, 1984; Norbis and Smith, 1986).

Recent theoretical advances in mathematical programming along with improvements in computer hardware and computing power have resulted in commercial software that can handle large-scale mathematical programming. In addition, we use new modeling ideas that incorporate an increasing number of realistic assumptions and still keep the size of the problem manageable. For example, Rabinowitz et al. (1991) propose a monolithic model formulation for production planning and scheduling in a multirobot assembly cell. They use a mixed-integer programming to exploit the advantages associated with a monolithic approach and still incorporate all realistic assumptions regarding the operations of the system. In addition, by exploiting certain structural properties of the problem, the formulation size can be reduced, further facilitating the solution of the problem. The model is comprehensive enough to allow for a higher level of decisions in the assignment of jobs and resources to multiple cells.

Samaddar et al. (1999) provide a monolithic approach to a resource sharing and scheduling problem in a computer-integrated manufacturing cell. In addition to providing a comprehensive and flexible formulation for the problem, they also offer a branch and bound solution procedure to find the optimal solution. This is by far the only approach available for solving a large-scale resource-sharing and scheduling problem with realistic assumptions of multiresource, multimode, nonpreemptive, and continuous time. However, Samaddar et al. (1999) do not examine the solution performance of the model in solving the mixed-integer programming.

In this paper, we provide a comprehensive experimental analysis on the solution performance in solving the monolithic formulated problem, following the work by Samaddar et al. (1999). Obtaining a good understanding and prediction of computational effort for complex scheduling problem is important for several reasons. First, it can help decision makers to gain insights of the impact of various factors and parameters on the problem complexity and solution effort, and therefore more effectively control the parameters in the actual decision making situation. It is important to point out that most of the scheduling literature generally reports the worst case performance of the solution algorithm which will not be a true indication of the actual impact of some factors because such performance measures focus only on extreme values and thus have a tendency to over-amplify the impact of the RSSP factors. We hope that through our research, we can provide more accurate assessment on the performance impact of various factors. Second, it can aid researchers to further refine the solution procedure and find more efficient solution techniques. Finally, information on the model performance under a variety of circumstances can ease the adoption of the model and its solution method for solving real world complex problems.

Experimental analyses for studying the effects of problem parameters on the performance of a solution procedure are common in the literature. For example, Patterson (1984) uses regression analysis to study the performance of various heuristic procedures for solving project scheduling problems. Parlar and Gerchak (1989) report a regression analysis in solving an inventory control problem for given values of the problem parameters. Srivastava and Benton (1990) conduct an analysis of variance (ANOVA) to study the impact of environmental factors such as cost structure and customer distribution on the performance of some heuristic location-routing solution procedures. Furthermore, Madu et al. (1990) perform a regression analysis to assess the influence of different resources and the coefficient of variation on various measures of performance in a maintenance system.

The remainder of this paper is organized as follows. In the next section, we briefly discuss the monolithic model and the solution procedure. Section 3 describes the experimental design and methodology. Section 4 then reports the results and statistical analysis. The insights gained from the experiment will also be discussed. Finally, Section 5 provides a summary and concluding remarks.

Section snippets

Model formulation and solution procedure

The general problem of resource-sharing and scheduling can be described as follows. Suppose that one has to perform a job consisting of a given set of operations using a number of resources. Precedence relationships among the operations restrict their processing order. The processing of an operation may require a subset of resources for each alternative processing mode. A resource may be used for a portion of the operation time. The processing time is assumed to be deterministic and continuous.

Experimental design

In this section, we lay out in detail our design of experiment in analyzing the effects of various factors on the performance of the solution process for the general resource-sharing and production planning problem. It is important to note that the literature contains no test data and similar study for the type of comprehensive RSSP problem addressed in this research. Due to the complexity of problem with a relatively large number of factors to be considered in the experimental study, we limit

Results

Sixteen RSSPs specified in the above design of experiment were solved repeatedly under each of the four objective functions , , , discussed earlier. Since the solution process first branches on a combination of modes, objective functions that are fully evaluated by the choice of the modes lend the problem solving to an interesting shortcut. The objective functions , , have such a property (see the discussion from Section 2). Therefore, the solution procedure is expected to have less effort

Concluding remarks

In this paper, we examined the performance of a branch and bound enumeration procedure in solving a monolithic mixed-integer linear programming formulation for a resource-sharing and scheduling problem. Since the formulation size explodes for a problem of even modest size, the use of generic mathematical programming codes to solve the formulation can be difficult. Although the customized branch and bound enumeration procedure proposed by Samaddar et al. (1999) offers a promising approach to

References (34)

  • R.L. Daniels et al.

    Single machine scheduling with controllable processing times and number of jobs tardy

    Operations Research

    (1989)
  • E.W. Davis

    Project scheduling under resource constraints: Historical review and categorization of procedures

    AIIE Transactions

    (1973)
  • M.A.H. Dempster et al.

    Analytical evaluation of hierarchical planning systems

    Operations Research

    (1981)
  • M. Garetti et al.

    On-line loading and dispatching in flexible manufacturing systems

    International Journal of Production Research

    (1990)
  • S.C. Graves

    Using lagrangean techniques to solve hierarchical production planning problems

    Management Science

    (1982)
  • A.C. Hax et al.

    Hierarchical integration of production planning and scheduling

  • J. Kimemia et al.

    Flow optimization in flexible manufacturing systems

    International Journal of Production Research

    (1985)
  • Cited by (17)

    • New lower bounds for solving a scheduling problem with resource collaboration

      2019, Computers and Industrial Engineering
      Citation Excerpt :

      This section describes the existing B&B algorithm that we use to solve the above RSSP and for which we provide and analyze new LBs in the next section. Our work uses the general framework of the B&B algorithm of Samaddar et al. (1999, 2005). The B&B algorithm contains two main steps: the assignment step, which guarantees a feasible selection of one mode for each operation, and the sequencing step, which guarantees a feasible sequence of operations on each resource and synchronizes the starting times of operations and their resource tasks.

    • A column generation based distributed scheduling algorithm for multi-mode resource constrained project scheduling problem

      2018, Computers and Industrial Engineering
      Citation Excerpt :

      However, such complexity reflects actual conditions. Resource-sharing and scheduling is an important area of research that has significant practical implications in production planning because efficient and effective use of available production resources is vital for the ever increasing competitiveness to the manufacturing as well as service industry (Pinto et al., 2009, 2013; Samaddar, Rabinowitz, & Zhang, 2005). Contrary to previous studies, which considers resource-sharing in just one factory, this paper considers the resource sharing among all the processors which can produce the same products.

    • Product Service Systems for Social Manufacturing

      2019, Springer Series in Advanced Manufacturing
    View all citing articles on Scopus
    View full text