Production, Manufacturing and LogisticsAn experimental analysis of solution performance in a resource sharing and scheduling problem
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)
- et al.
Coefficient of variation: A critical factor in maintenance float policy
Computers and Operations Research
(1990) - et al.
Control of a production system with variable yield and random demand
Computers and Operations Research.
(1989) - et al.
Solving a large-scale industrial scheduling problem using MILP combined with a heuristic procedure
European Journal of Operational Research
(2002) - et al.
Resource sharing and scheduling for cyclic production in a computer-integrated manufacturing cell
Computers and Industrial Engineering: An International Journal
(1999) - et al.
The location routing problem: Considerations in physical distribution systems
Computers and Operations Research.
(1990) - et al.
Hierarchical production planning: A single stage system
Operations Research
(1981) - et al.
A hierarchical production planning and scheduling model
Decision Sciences
(1992) - et al.
Capacity cost and scheduling analysis for a multiproduct flexible manufacturing cell
International Journal of Production Research
(1987) - et al.
A multiobjective evaluation of flexible manufacturing system loading heuristic
International Journal of Production Research
(1990) - et al.
A methodical approach to the flexible-manufacturing-system batching, loading and tool configuration problems
International Journal of Production Research
(1990)
Single machine scheduling with controllable processing times and number of jobs tardy
Operations Research
Project scheduling under resource constraints: Historical review and categorization of procedures
AIIE Transactions
Analytical evaluation of hierarchical planning systems
Operations Research
On-line loading and dispatching in flexible manufacturing systems
International Journal of Production Research
Using lagrangean techniques to solve hierarchical production planning problems
Management Science
Hierarchical integration of production planning and scheduling
Flow optimization in flexible manufacturing systems
International Journal of Production Research
Cited by (17)
Product service systems for social manufacturing: A new service system with multi-provider
2019, IFAC-PapersOnLineNew lower bounds for solving a scheduling problem with resource collaboration
2019, Computers and Industrial EngineeringCitation 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 EngineeringCitation 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.
A genetic algorithm-based approach for solving the resource-sharing and scheduling problem
2009, Computers and Industrial EngineeringCould 3D food printing help to improve the food supply chain resilience against disruptions such as caused by pandemic crises?
2021, International Journal of Food Science and TechnologyProduct Service Systems for Social Manufacturing
2019, Springer Series in Advanced Manufacturing