Capacity planning by the dynamic multi-resource generalized assignment problem (DMRGAP)

The allocation of available capacity among competing demand and users is a problem encountered in areas such as job shop scheduling, the trucking industry and distributed computer systems. In all these areas a model known as the Multi-Resource Generalized Assignment Problem (MRGAP) has been proposed as a tool to assign available capacity among the competing applications. In this paper we extend the MRGAP model to the case where demand varies over time and capacity assignments are dynamic. We show that the extended model can be used for strategic capacity planning and we develop efficient solution procedures to solve the dynamic version of MRGAP.     

On modelling the maximum workload allocation for parallel unrelated machines with setups

Consider a manufacturing process in which a group of machines (or people) perform a single operation on a number of different parts. The processing time depends on both the part and the machine. In addition, each machine requires significant setup time between processing different part types. The problem consists of obtaining a feasible allocation of parts to machines such that the makespan (i.e. greatest machine workload) is minimized. We present two equivalent 0–1 models. The first model arises by considering the assignment of individual parts to machines. It is amenable to Lagrangian decomposition techniques. The second model is more hierarchical in nature; it considers the two options of assigning an entire part type to a single machine, or of splitting the type across machines. The second model is more amenable than the first to branch-and-bound techniques. We report about our computational experience for finding lower bounds of the optimal solution by appending violated cuts and, ultimately, obtaining the optimal solution of real-life problems.     

The equilibrium generalized assignment problem and genetic algorithm

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.     

Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions

The capacitated lot sizing and loading problem (CLSLP) deals with the issue of determining the lot sizes of product families/end items and loading them on parallel facilities to satisfy dynamic demand over a given planning horizon. The capacity restrictions in the CLSLP are imposed by constraints specific to the production environment considered. When a lot size is positive in a specific period, it is loaded on a facility without exceeding the sum of the regular and overtime capacity limits. Each family may have a different process time on each facility and furthermore, it may be technologically feasible to load a family only on a subset of existing facilities. So, in the most general case, the loading problem may involve unrelated parallel facilities of different classes. Once loaded on a facility, a family may consume capacity during setup time. Inventory holding and overtime costs are minimized in the objective function. Setup costs can be included if setups incur costs other than lost production capacity. The CLSLP is relevant in many industrial applications and may be generalized to multi-stage production planning and loading models. The CLSLP is a synthesis of three different planning and loading problems, i.e., the capacitated lot sizing problem (CLSP) with overtime decisions and setup times, minimizing total tardiness on unrelated parallel processors, and, the class scheduling problem, each of which is NP in the feasibility and optimality problems. Consequently, we develop hybrid heuristics involving powerful search techniques such as simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) to deal with the CLSLP. Results are compared with optimal solutions for 108 randomly generated small test problems. The procedures developed here are also compared against each other in 36 larger size problems.     

A GRASP for simultaneously assigning and sequencing product families on flexible assembly lines

This paper introduces a new model and solution methodology for a real-world production scheduling problem arising in the electronics industry. The production environment is a high volume, just-in-time, make-to-order facility with volatile demand over many product families that are assembled on flexible lines. A distinguishing characteristic of the problem is the presence of non-traditional sequence-dependant setup costs, which complicate our ability to find high-quality solutions. The scheduling problem arose when product variety exceeded the mix that the existing lines could accommodate. A nonlinear integer programming formulation is presented for the problem of minimizing setup costs, and a greedy randomized adaptive search procedure (GRASP) is developed to find solutions. To select the GRASP parameter values, an efficient, space-filling experimental design method is used based on nearly orthogonal Latin hypercubes. The proposed methodology is tested on actual factory data and compared to a prior heuristic presented in the literature; our heuristic provides a cost savings in 7 out of the 10 cases examined, and an average improvement of 17.39 % which is shown to be highly statistically significant. This improvement is due in part to the introduction of a pre-processing step to determine preferential and non-preferential line assignment information.     

Interactive fuzzy programming for two-level linear and linear fractional production and assignment problems: A case study

In this paper, we deal with actual problems on production and work force assignment in a housing material manufacturer and a subcontract firm. We formulate two kinds of two-level programming problems: one is a profit maximization problem of both the housing material manufacturer and the subcontract firm, and the other is a profitability maximization problem of them. Applying the interactive fuzzy programming for two-level linear and linear fractional programming problems, we derive satisfactory solutions to the problems. After comparing the two problems, we discuss the results of the applications and examine actual planning of the production and the work force assignment of the two firms to be implemented.     

Multiple machine continuous setup lotsizing with sequence-dependent setups

We address the short-term production planning and scheduling problem coming from the glass container industry. A furnace melts the glass that is distributed to a set of parallel molding machines. Both furnace and machine idleness are not allowed. The resulting multi-machine multi-item continuous setup lotsizing problem with a common resource has sequence-dependent setup times and costs. Production losses are penalized in the objective function since we deal with a capital intensive industry. We present two mixed integer programming formulations for this problem, which are reduced to a network flow type problem. The two formulations are improved by adding valid inequalities that lead to good lower bounds. We rely on a Lagrangian decomposition based heuristic for generating good feasible solutions. We report computational experiments for randomly generated instances and for real-life data on the aforementioned problem, as well as on a discrete lotsizing and scheduling version.     

带时变生产成本的易变质经济批量模型的最优策略分析

考虑了具有时变生产成本的易变质产品经济批量模型．有限计划期内,单位生产成本、生产率以及需求率假定为时间的连续函数,生产固定成本则具有遗忘效应现象．当不允许缺货时,建立了以总成本最小为目标的混合整数优化模型并证明了此问题最优解的相关性质．对于此问题的特殊情形,将成本函数中的离散型变量松弛为连续型变量,通过分析其最优解的存在性及唯一性,求解了此最优解,将其作为初始值设计了求取一般情形最优解的有效算法．最后通过算例验证了理论结果的有效性．     

A bicriteria parallel machine scheduling with a learning effect of setup and removal times

In studies on scheduling problems, generally setup times and removal times of jobs have been neglected or by including those into processing times. However, in some production systems, setup times and removal times are very important such that they should be considered independent from processing times. Since, in general jobs are done according to automatic machine processes in production systems processing times do not differ according to process sequence. But, since human factor becomes influential when setup times and removal times are taken into consideration, setup times will be decreasing by repeating setup processes frequently. This fact is defined with learning effect in scheduling literature. In this study, a bicriteria m-identical parallel machines scheduling problem with a learning effect of setup times and removal times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and total tardiness. A mathematical programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 15 jobs and five machines. We also proposed three heuristic approaches for solving large jobs problems. According to the best of our knowledge, no work exists on the minimization of the weighted sum of total completion time and total tardiness with a learning effect of setup times and removal times.     

The shift team formation problem in multi-shift manufacturing operations

This paper addresses the problem of assigning operators to teams that work in 1-, 2-, or 3-daily-shift systems. The problem was motivated by, and illustrated with a case situation encountered in Dutch manufacturing industry. The problem addressed forms an extension of cell formation problems which are currently in the phase of addressing labor-related issues in cell design. A generalized goal problem formulation is presented to address multiple, conflicting objectives covering cross-training of workers, ensuring adequate levels of labor flexibility and minimizing labor-related costs. The proposed solution procedure consists of two phases. In the first phase, shift systems, in which applicable machines and the sizes of each shift team are identified. The next phase deals with assignment of operators to various teams and identification of specific cross-training needs for various workers. This phase involves the use of interactive goal programming. The methodology is illustrated by a numerical example derived from the case situation.     

A study of decision support models for online patient-to-room assignment planning

The present paper studies patient-to-room assignment planning in a dynamic context. To this end, an extension of the patient assignment (PA) problem formulation is proposed, for which two online ILP-models are developed. The first model targets the optimal assignment for newly arrived patients, whereas the second also considers future, but planned, arrivals. Both models are compared on an existing set of benchmark instances from the PA planning problem, which serves as the basic problem setting. These instances are then extended with additional parameters to study the effect of uncertainty on the patients’ length of stay, as well as the effect of the percentage of emergency patients. The results show that the second model provides better results under all conditions, while still being computationally tractable. Moreover, the results show that pro-actively transferring patients from one room to another is not necessarily beneficial.     

Parallel machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

Simultaneous lotsizing and scheduling on parallel machines

This paper addresses the simultaneous lotsizing and scheduling of several products on non-identical parallel production lines (heterogeneous machines). The limited capacity of the production lines may be further reduced by sequence dependent setup times. Deterministic, dynamic demand of standard products has to be met without back-logging with the objective of minimizing sequence dependent setup, holding and production costs.The problem is heuristically solved by combining the local search metastrategies threshold accepting (TA) and simulated annealing (SA), respectively, with dual reoptimization. Such a solution approach has already proved to be successful for the single machine case. The solution quality and computational performance of the new heuristics are tested by means of real-world problems gathered from industry.     

一类特殊二维0-1规划的广义指派模型求解

二维0-1整数规划模型应用广泛,对广义指派问题的研究,解决了一些二维0-1整数规划问题.但有些实际问题具有特殊上限约束,目前还没有对应的方法.针对该实际情形,本文建立了相应的数学模型,利用对指派模型的推广,求得问题最优解,从理论上解决了这一类特殊约束二维0-1整数规划的最优解求取问题.并通过算例说明了方法的使用.     

Heuristic Interpretation of Infeasible Solutions to a Production Scheduling Problem in Cigarette Manufacture

In this paper an end-user Infeasibility Resolution Heuristic (IRH) is developed to assist managers and production schedulers in the evaluation and interpretation of infeasible solutions arising from the use of a production scheduling model of a tobacco processing plant. The primary aim of the model is initially to determine whether the forecast annual demand for tobacco products can be met by the plant, and if not what must be done. Having determined that the demanded quantities are feasible, the model is then used to arrive at a production schedule such that the minimum number of machines are used in the entire process for the planning period (the model is a monthly one linked together by the closing stock equations for up to 12 months ahead). The operations of the plant modelled include the selection of the appropriate blend of leaf, assignment of the forecast product demand to suitable making machines, production of the required quantity of filters, assignment of the cigarettes produced to specific packers and then the determination as to whether the final product produced in the current period will be used to satisfy the current month's demand or demand in the future. The problem of sequencing the monthly production once the production schedule is determined has not been dealt with in this paper.     

Fixed interval scheduling: Models,applications, computational complexity and algorithms

The defining characteristic of fixed interval scheduling problems is that each job has a finite number of fixed processing intervals. A job can be processed only in one of its intervals on one of the available machines, or is not processed at all. A decision has to be made about a subset of the jobs to be processed and their assignment to the processing intervals such that the intervals on the same machine do not intersect. These problems arise naturally in different real-life operations planning situations, including the assignment of transports to loading/unloading terminals, work planning for personnel, computer wiring, bandwidth allocation of communication channels, printed circuit board manufacturing, gene identification and examining computer memory structures. We present a general formulation of the interval scheduling problem, show its relations to cognate problems in graph theory, and survey existing models, results on computational complexity and solution algorithms.     

A robust optimization approach to wine grape harvesting scheduling

Optimization models are increasingly being used in agricultural planning. However, the inherent uncertainties present in agriculture make it difficult. In recent years, robust optimization has emerged as a methodology that allows dealing with uncertainty in optimization models, even when probabilistic knowledge of the phenomenon is incomplete. In this paper, we consider a wine grape harvesting scheduling optimization problem subject to several uncertainties, such as the actual productivity that can be achieved when harvesting. We study how effective robust optimization is solving this problem in practice. We develop alternative robust models and show results for some test problems obtained from actual wine industry problems.     

Group technology in a hybrid flowshop environment: A case study

This paper addresses the problem of products grouping in the tile industry. This production system can be classified as a three-stage hybrid flowshop with sequence dependent and separable setup times. Main objective has been to identify a set of families integrated by products with common features. This classification would help Production Managers to minimize changeover time, allowing them to further reduce production times. The basic concept of “exploiting similarities”, taken from the Group Technology (GT) philosophy, has been used to address the problem in a creative way. A new “coefficient of similarity” between each of the products, has been defined and used as a parameter, allowing products to be grouped through a heuristic method. This research has already been applied in the framework of a real case, getting quite positive results (actual reduction in both setup and production costs, easier long-horizon planning and short-horizon scheduling, more accurate set up time estimates for new products, etc.).     

Multi-plant production planning in capacitated self-configuring two-stage serial systems

This research deals with a capacitated master production planning and capacity allocation problem for a multi-plant manufacturing system with two serial stages in each plant. We consider both cases in which a decoupling buffer is allowed or not between the two stages. Peculiar to the system considered is the capability of dynamically self-configuring its layout when buffering is disallowed, in the sense that, for each production run, different parallel machines in the second stage are grouped together and serially connected to a machine in the first stage. Although setup times and costs are considered negligible in our model, yet binary setup variables are introduced in order to account for minimum lot-sizes. The resulting mixed {0,1} linear programming model is solved by means of LP-based heuristic algorithms. The proposed modeling and solution procedure has been applied to problem instances originating from a real-world application, showing good results in practice.     

Comparative evaluation of MILP flowshop models

This paper investigates the performance of two families of mixed-integer linear programing (MILP) models for solving the regular permutation flowshop problem to minimize makespan. The three models of the Wagner family incorporate the assignment problem while the five members of the Manne family use pairs of dichotomous constraints, or their mathematical equivalents, to assign jobs to sequence positions. For both families, the problem size complexity and computational time required to optimally solve a common set of problems are investigated. In so doing, this paper extends the application of MILP approaches to larger problem sizes than those found in the existing literature. The Wagner models require more than twice the binary variables and more real variables than do the Manne models, while Manne models require more constraints for the same sized problems. All Wagner models require much less computational time than any of the Manne models for solving the common set of problems, and these differences increase dramatically with increasing number of jobs and machines. Wagner models can solve problems containing larger numbers of machines and jobs than the Manne models, and hence are preferable for finding optimal solutions to the permutation flowshop problem with makespan objective.