Lot sizing and scheduling — Survey and extensions <s> Continuous time lot sizing and scheduling <s> A batch sequencing model with sequence-dependent setup-times and -costs is used to compare modeling and solving with two different general solvers. “Conceptual models” are implemented and solved using the constraint programming language CHARME. The mixed-integer-programming (MIP) formulation of the same problem is solved with OSL, a state-of-the-art MIP solver. We compare modeling in both solvers and the performance of the constraint versus the mixed-integer programming solver. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499. <s> BIB001 </s> Lot sizing and scheduling — Survey and extensions <s> Continuous time lot sizing and scheduling <s> 1 Introduction.- 1.1 Motivation of the Planning Problem.- 1.2 Background and Related Work.- 1.3 Case Description.- 1.4 Chapter Synopsis.- 2 Description of the Problems.- 2.1 Batching Types and Literature Review.- 2.2 Notation, Basic Definitions and [?/?/?] Descriptor.- 2.3 Single-Machine Case.- 2.4 Multi-Level Product Structures and Parallel Machines.- 2.5 Complexity Analysis.- 2.6 Structural Properties.- 2.7 Instance Generator.- 3 Single-Machine Case.- 3.1 Basic Enumeration Scheme.- 3.2 Item Availability - Preemptive Batching.- 3.2.1 Branch&Bound.- 3.2.2 Dynamic Programming.- 3.2.3 Construction and Improvement.- 3.2.4 Computational Results.- 3.3 Item Availability - Nonpreemptive Batching.- 3.3.1 Branch&Bound.- 3.3.1.1 Minimum Cost Schedule of a Sequence.- 3.3.1.2 Dominance Rules.- 3.3.2 Genetic Algorithm for Sequence Independent Setups.- 3.3.3 Computational Results.- 3.4 Batch Availability.- 3.4.1 Branch&Bound.- 3.4.1.1 Late Schedule of a Sequence.- 3.4.1.2 Dominance Rule.- 3.4.2 Genetic Algorithm for Sequence Independent Setups.- 3.4.3 Computational Results.- 3.4.4 Genetic Algorithm for the Flow-Shop Case.- 4 Discrete Lotsizing and Scheduling.- 4.1 Discrete Lotsizing and Scheduling Problem.- 4.2 Equivalence of DLSP and BSP.- 4.3 Comparison with Variants of the DLSP.- 4.3.1 Sequence Independent Setup Times and Costs (SISTSC).- 4.3.2 Sequence Dependent Setup Costs (SDSC).- 4.3.3 Sequence Dependent Setup Times and Costs (SDSTSC).- 4.3.4 Single-Level Batch Availability (BA).- 4.3.5 Two-Level Batch Availability (BA2LV).- 4.4 Conclusions.- 5 Multi-Level and Parallel Machine Case.- 5.1 Multi-Level Case.- 5.1.1 Single-Machine.- 5.1.2 Multi-Machine.- 5.1.3 Preliminary Computational Results.- 5.2 Parallel Machines.- 6 Artificial Intelligence Approaches.- 6.1 Introduction.- 6.2 Model Formulations.- 6.3 Performance Comparison.- 6.4 Conclusions.- 7 Summary and Future Work.- Appendix A Setup Matrices for the Instance Generator.- List of Notation.- List of Abbreviations.- List of Figures.- List of Tables. <s> BIB002 </s> Lot sizing and scheduling — Survey and extensions <s> Continuous time lot sizing and scheduling <s> We formulate a general sequencing problem that includes two classes of jobs with setup times, setup costs, holding costs, and deadlines. The formulation is unique in its explicit recognition of the opportunities to exploit productive capacity increases due to batching. An algorithm based on tabu search is then used as a solution method. Computational results are presented that suggest that the algorithm is effective. (SEQUENCING, TABU SEARCH) <s> BIB003
In BIB002 and [63] this idea is picked up. Each demand is characterized by its deadline and its size. Demands are interpreted as jobs and the demand size determines the processing time of a job. An important assumption is that the capacity, e.g. the speed of the machine, is constant over time, and thus, the processing time of a job does not depend on the schedule. Another fundamental assumption is that jobs are not allowed to be split, which means that a certain demand must always be processed in one piece. Of course, several demands (= jobs) for the same item may be grouped together to form one lot and to save setup costs. Due to this assumption, the problem is referred to as a batching and scheduling problem (BSP) rather than a lot sizing and scheduling problem. To give a formal presentation of the BSP, let us assume the following: a unique number is assigned to each job to identify it. Hence, if there are N demands to be fulfilled, we can assume without loss of generality that 1 ..... N are the job numbers. Furthermore, 0 and N + 1 are the numbers of dummy jobs which are to be scheduled as the first and the last job, respectively. A solution of the BSP is uniquely characterized by the sequence in which jobs are to be scheduled and by the completion time for each job. These decision variables are specified in Table 10 . The parameters are given in Table 11 . A mixed-integer program for the BSP can now be given as follows:  The objective (38) is to minimize the total sum of setup and holding costs. Note, due to the definition of the Xnk variables it is quite easy to incorporate sequence dependencies into the model. The holding costs for a job are calculated by multiplying the holding costs for the corresponding item with the processing time of the job (and with the earliness of the job). This is because a demand is fulfilled if the whole job which represents that particular demand is processed. Eq. (39) makes sure that each job has exactly one successor; only job N+I has none. Analogously, Eq. (40) guarantee that each job has exactly one predecessor; only job 0 has none. Due to restrictions (41), jobs do not overlap. Constraints (41) in combination with constraints (39) and (40) define a total order among the jobs. Backlogging cannot occur because of the inequalities (42). Constraints (43) are the binary conditions, and restrictions (44) are the non-negativity conditions for the decision variables. The completion time of the dummy job 0 is zero as stated in Eq. (45). In this BSP model formulation, idle periods among jobs for the same item do not cause additional setups, which is similar to the CSLP, the PLSP, and the GLSP as stated above. A variety of BSP models as well as solution methods for it are discussed in BIB002 . Under restrictive assumptions such as equal holding costs for all items or unit processing times for all items, efficient procedures for computing the optimum sequence are derived. For a variant of the BSP it can be shown that it is equivalent to the DLSP, and thus, solution procedures for the BSP can be employed to solve DLSP instances [63] . By utilizing the idea of unique position numbers to which jobs are to be assigned (compare the GLSP model formulation), a model can be formulated which uses position numbers as decision variables and which is amenable to the constraint (logic) programming paradigm (see BIB001 for a similar idea where decision variables are used as indices; a related idea can be found in BIB003 ). With respect to the example in Section 1.4 the BSP, too, can be seen as an approach to integrate phases I-III. And again, as long as multi-level gozinto structures are not taken into account, using the BSP level by level does not guarantee feasible solutions. Minimum lead times can easily be incorporated into the model.