This paper addresses the multi-product, finite horizon, static demand, sequencing, lot sizing and scheduling problem in a job shop environment where the planning horizon length is finite and fixed by management. The objective pursued is to minimize the sum of setup costs, and work-in-process and finished products inventory holding costs while demand is fulfilled without backlogging. We propose a new and efficient cyclic scheduling solution framework, called the multiple cycle (MC) method, based on the assumption that the cycle time of each product is an integer multiple of a basic period. This method relies on a decomposition approach which decomposes the problem into an assignment sub-problem, a sequencing sub-problem and a lot sizing and scheduling sub-problem. To evaluate its performance, the MC method was compared to the common cycle method and numerical results show that it performs better, as expected. However, the magnitude of improvement varies between 4% and 8% depending on the structure of the problems.
This paper addresses the problem of making sequencing, lot sizing and scheduling decisions for several products, say n, manufactured through a job shop where all parameters are deterministic and constant over a given planning horizon length, say H, which is assumed to be fixed by management. The objective pursued is to minimize the sum of setup costs, work-in-process (WIP) inventory holding costs and finished products inventory holding costs while a given demand is fulfilled without backlogging. We consider a job shop with m machines and assume that there is only one machine of each type and that each product i has a unique serial route through the shop which will be indicated by an ordered subset of machines and denoted by ρ(i,.); in other words, we assume that routing decisions have been made and, based on some criteria, a unique serial route has been chosen for each product. In addition, we assume that preemption is not allowed. To solve this problem, we assume that the cycle time of each product i, say Ti, is an integer multiple, say mi, of a basic period F; that is, Ti=miF for all i. In addition, we require that the basic period F be such that the planning horizon H is an integer multiple of the global cycle MF, that is, H=ξMF where ξ is an integer and M denotes the least common multiple (LCM) of mi's. This problem can be formulated as a mixed non-linear program that simultaneously determines all the relevant decisions. However, for large or even medium size instances, the solution of this model may require a prohibitive amount of computational time. Consequently, in this paper, we propose a solution method, called the multiple cycle (MC) method, which decomposes the problem into three sub-problems; namely, an assignment sub-problem, a sequencing sub-problem and a lot sizing and scheduling sub-problem. The first two sub-problems are solved using heuristics while the third sub-problem is solved to optimality. Throughout this paper, we will use the notation given in Fig. 1.
Full-size image (31 K)
Fig. 1.
Basic notation.
Figure options
To the best of our knowledge, the only contribution to this problem is reported in Ouenniche and Boctor [1]. Recall that the classical job shop problem has attracted the attention of many researchers (e.g., [3], [4], [5], [6], [7], [8], [9] and [10]). This problem consists of determining, for a given set of non-splittable jobs, the execution sequences and the starting dates so as to optimize some objective function. However, this problem is quite different from the one considered in this paper, as the classical job shop problem does not deal with lot sizing issues. Attention has also been paid to the lot size issue in the stochastic version of the job shop problem but without simultaneously considering the sequencing and scheduling phase (see [11] and [12]). A recent exception to this is the work of Lambrecht et al. [13] who integrate lot sizing, release and sequencing decisions through a hierarchical approach with feedback adjustment mechanisms.
The remainder of this paper is organized as follows. In Section 2, we present the general framework of the MC method. In Section 3, we show how to assign products to basic periods. In Section 4 we show how to determine sequencing decisions and in Section 5 we present a mathematical formulation of the lot sizing and scheduling subproblem and show how to solve it. Finally, Section 6 provides some numerical results and Section 7 presents the conclusions of this research.
In this paper, we proposed a new and efficient heuristic, called the multiple cycle (MC) method, to solve the multi-product, finite horizon, static demand, sequencing, lot sizing and scheduling problem in a deterministic job shop environment where the planning horizon length is fixed by the management team. This heuristic assumes that products cycle times are integer multiples of a basic period and requires that the basic period be such that the planning horizon length is an integer multiple of the global cycle length. The MC method decomposes the problem into three sub-problems: an assignment sub-problem, a sequencing sub-problem and a lot sizing and scheduling sub-problem. The first two sub-problems are solved using heuristics while the third one is solved to optimality using mathematical programming. Actually, the sequencing, lot sizing and scheduling subproblem in embedded in the assignment subproblem to evaluate an assignment of products to basic periods and the corresponding vector of time multipliers whereas the lot sizing and scheduling subproblem is embedded in the sequencing subproblem to evaluate sequencing decisions. The MC method was compared to the common cycle method and numerical results show that it performs much better. However, the magnitude of performance depends on the problem structure.
