شاخه تطبیقی ​​و روش های محدود برای تبدیل تولید کارگاهی به تولید جریان

In this paper we address the problem of transforming a job shop layout into a flow shop with the objective of minimizing the length of the resulting flow-line. First, we present five properties of the problem under consideration that are employed for constructing a branch and bound algorithm. The approach is named adaptive since the development of the children nodes depends on the particular instance in order to try tightening the lower bounds and hence performing faster. The computational experiments carried out show the approach to be effective for a variety of problem sizes.

A flow shop consists of a sequence of machines (or workplaces) through which several products (or jobs) move in order to be processed. The flow of all products through the machines always follows the same direction, although it is possible that some job does not have to be processed in a particular machine of the flow shop. The flow shop configuration has a number of advantages over the more general job shop, i.e.: • Minimal material handling, easier conveyance between cells, and greater control of cell activities (Vakharia & Wemmerlov, 1990). • Little incidences when backtracking due to the simplified flow Dumolien and Santen, 1983. • Ease of control (Krajewski, King, Ritzman, & Wong, 1987). • The fact that modern pull-based manufacturing techniques are not well suited to a job shop, while being fully applicable to a flow shop (Hall, 1983). It is known that the job shop layout is the common configuration in many manufacturing scenarios (Thompkins, 1984). Therefore, the eventual transformation of their job shops into flow shops may be of interest for manufacturing companies. Precisely this transformation is considered relevant in the context of the Supply Chain Management (SCM), where ’attempts should be made to shift job shop manufacturing in the direction of object-oriented flow shop production’ (Knolmayer, Mertens, & Zeier, 2002). Two objectives seem to be desirable when transforming a job shop layout into a flow shop (Framinan, 2005): minimizing the length of the resulting flow shop, and minimizing the additional investment required for the transformation. Although these two objectives are somewhat related, it is clear that they are only equivalent in the case of machines which similar purchasing price. In fact, it seems that additional investment costs minimization stresses the costs of the transformation while length minimization is aimed to a better performance of the resulting flow line. This is because the minimization of the length of the flow shop serves to minimize the lead times of the operations in the resulting flow shop, which in turn implies lower inventory levels and lower capital costs (Kimms, 2000). Since the duplication of machines is very costly, it seems clear that, in principle, the lesser the machine investment, the more attractive is the approach. In a series of experiments for small problem instances, it has been found that the length of the resulting flow shop grows at a small ratio with the number of jobs (Framinan & Ruiz-Usano, 2002). As a consequence, the approach is not very costly if the number of jobs is high as compared to the number of machines and the routings of the jobs are not so different. Note that the last situation is common for many real-life job shops (Guinet & Legrand, 1998). Therefore, in this paper we focus our attention on the problem of, given a number of jobs and their routing matrix, find a flow shop layout of minimal length in which all these jobs can be processed. Note that the aim of the problem is a layout transformation and not a decomposition approach for scheduling such as the one presented e.g. in Rabenasolo, Zeng, and Happiette (1998) or in Guinet and Legrand (1998). For instance, in the latter reference, the job shop scheduling problem is tackled by re-ordering the machines so the original problem is transformed into the problem of scheduling jobs in a flow shop with precedence constraints. The objective of this transformation is to minimize the number of jobs with precedence constraints. Once this transformation is achieved, the so-obtained flow shop scheduling problem is solved and the solution is converted into a solution for the original job shop. In this sense, their approach may be seen as a virtual layout transformation in contrast to the physical layout transformation suggested here. Additionally, the approach by Guinet and Legrand can be seen as well as a physical layout transformation of a job shop into a flow shop with precedence constraints subject to non additional machine investment. From this viewpoint, it is clear that some relationship exists between Guinet and Legrand’s approach and the problem under consideration. This connection (or complementarity) is addressed in the final section of the paper. The problem of transforming job shops into flow shop with the objective of length minimization is also referred as the Shortest Common Supersequence (SCS) problem. It has been proven that that this problem is NP-hard (see Raiha & Ukkonen, 1981, or Timkovsky, 1990). As a consequence, most of the research has been devoted to develop heuristics for the problem, such as the works by Branke et al., 1998, Framinan and Ruiz-Usano, 2002, Fraser et al., 1995, Jiang and Li, 1995, Kimms, 2000 and Michel and Middendorf, 1999, or Framinan (2005), among others. With respect to exact approaches, Timkovsky develops a dynamic programming procedure for solving the SCS problem valid only for very small problem sizes. Referring specifically to exact approaches for the problem of transforming job shops into flow shops, Kimms (2000) and Framinan and Ruiz-Usano (2002) two different integer programming models are proposed. In the latter reference, a basic branch and bound algorithm loosely based on Timkovsky’s work is presented. Their approach is not efficient and its purpose was obtaining exact benchmarks for small problem instances in order to test the performance of specific heuristic procedures designed for this problem. In this paper, we first present a number of properties of the problem under consideration. This allows obtaining lower bounds in order to construct a branch and bound approach. This approach is later refined in order to take advantage of the symmetry of the problem and obtain tighter lower bounds. The subsequent computational experience shows the approach to be effective for a variety of problem sizes. Finally, conclusions and future research lines are presented.

In this paper, we tackle the problem of transforming a job shop into a flow line by adding and/or re-ordering the existing machines with the objective of minimizing the length of the resulting flow line. Given the complexity of the problem, the literature on the topic was mainly focused on finding good approximate solutions, being the exact approaches only capable to solve small problem instances. Nevertheless, given the potentially high investments involved – i.e. purchase of additional machines –, it seems desirable to investigate in exact methods capable to obtain optimal solutions. With this aim, we first present a number of specific properties for the problem under consideration. These properties are then embedded into a branch-and-bound procedure that is thus capable to generate tight lower bounds and to reduce the search space. The computational experience carried out shows that the proposed algorithm may solve problem instances of realistic sizes, and that the adaptive version makes an efficient use of the symmetry property of the problem under consideration and considerably tightens the lower bounds. Besides, it is likely than the practical applications of the procedure will yield better results that those shown here since the test bed provides more difficult job shop instances that those usually found in practice. The problem addressed here consists on obtaining (i.e. no recirculation of jobs is allowed). This is in contrast to other works (e.g. Guinet and Legrand (1998)) where machines are sorted in order to obtain flow shops with precedence constraints. Both approaches represent two extreme points: in Guinet and Legrand’s approach there is no additional machine investment at the expenses of obtaining a layout which is more difficult to operate in terms of material handling and control. In contrast, the approach addressed here allows obtaining a pure flow shop which is easier to operate, but at the expenses of a (possibly high) machine investment. It is likely that companies wish to balance both aspects, and consequently adopt intermediate solutions of near-pure flow shops with little additional investments. We believe that addressing these combined objectives is worth deserving future research. Additionally, we have already discussed that different routings could be implemented for a single solution. These different routings may not be all equally desirable with respect to aspects such as workload balancing, or robustness of the resulting flow line. Combining these and other objectives together with the reduction of the flow line length (see Mansour, Husseini, and Newman, 2000 for a survey of multi-criteria cell design) constitute also areas of research interest.