基于约束规划求解车辆调度问题

在约束规划基础上,结合启发式方法,提出了一个求解集送货问题的新思路,并给出了具体的带有时间窗的集送货一体化问题的算例,求出了较高质量的满意解。     

Constrained resource project scheduling subject to material constraints

Constrained resource project scheduling techniques schedule project activities subject to finite constraints on the availability of non-storable resources such as labor and equipment without consideration of constraints resulting from material requirements. Projects are frequently delayed and resources are wasted when project activities are delayed due to material shortages. A heuristic procedure is presented here for scheduling large projects subject to the availability of all necessary resources, including materials, manufactured components, facilities, equipment and labor as well as the acquisition lead times required by these resources. Results are listed for tests involving both benchmark and actual problems.     

Scheduling spatially distributed jobs with degradation: Application to pothole repair

This paper considers scheduling spatially distributed jobs with degradation. A mixed integer programming (MIP) model is developed for the linear degradation case in which no new jobs arrive. Properties of the model are analyzed, following which three heuristics are developed, enhanced greedy, chronological decomposition and simulated annealing. Numerical tests are conducted to: (i) establish limits of the exact MIP solution, (ii) identify the best heuristic based on an analysis of performance on small problem instances for which exact solutions are known, (iii) solve large problem instances and obtain lower bounds to establish solution quality, and (iv) study the effect of three key model parameters. Findings from our computational experiments indicate that: (i) exact solutions are limited to instances with less than 14 jobs; (ii) the enhanced greedy heuristic followed by the application of the simulated annealing heuristic yields high quality solutions for large problem instances in reasonable computation time; and (iii) the factors “degradation rate” and “work hours” have a significant effect on the objective function. To demonstrate applicability of the model, a case study is presented based on a pothole repair scenario from Buffalo, New York, USA. Findings from the case study indicate that scheduling spatially dispersed jobs with degradation such as potholes requires: (i) careful consideration of the number of servers assigned, degradation rate and depot location; (ii) appropriate modeling of continuously arriving jobs; and (iii) appropriate incorporation of equity consideration.     

An experimental comparison of human schedulers and heuristic algorithms for the traveling salesman problem

Vehicle routing and scheduling for laundry, courier, mail, and other service operations is a significant service industry problem. Several computer-based heuristic algorithms have been developed to assist schedulers in developing efficient delivery (and pick up) vehicle routes. This paper reports the results of an experiment that compared the performance of inexperienced human schedulers and seven heuristic vehicle routing algorithms. A large set of traveling salesman test problems ranging in size from 10 to 80 customers was used in the experiment. The results of the experiment suggest that inexperienced, untrained human schedulers can consistently find traveling salesman solutions as good as or better than all but one of the seven heuristic algorithms tested (including the widely used ClarkeWright distance saved heuristic and the recently published largest-angle insertion heuristic). The human schedulers found traveling salesman routes as good as the best heuristic tested (Lin 's 3-optimal) in 29 percent of the test problems. On average, the human schedulers' solution distances were only 2.8 percent above the 3-optimal heuristic solution distances.     

A mixed-integer linear programming decision model for aquaculture

This paper presents a mathematical model for use in aquaculture, the rearing of aquatic animals in a controlled environment. The model addresses the real-world strategic planning requirements of an emerging technology as well as the short- and long-term production scheduling requirements of a mature aquaculture facility. A solution procedure for large-scale problems is described and tested, and an illustrative application is presented.     

Evaluation of scheduling techniques for solving flowshop problems with no intermediate storage

The flowshop scheduling problem with no intermediate storage (NIS problem) was studied in this research. This problem, a modification of the classical flowshop scheduling problem, arises when a set of jobs, once started, must be processed with no wait between consecutive machines. By eliminating the need for intermediate storage, reduction of capital investment in work-in-process inventory can be achieved. This approach can be practically applied to a steel mill, in which the metal should be continuously processed in order to maintain high temperature, as well as many other similar processes.To provide insight into selecting an appropriate scheduling technique for solving the NIS problem, six methods were compared in terms of the quality and efficiency of the scheduling solutions they produced. The quality of solution was measured by makespan and the efficiency of solution was measured by the computational time requirements. The six methods examined in this study included: the Gupta algorithm, the Szwarc algorithm, an integer linear programming method, the Campbell et al. algorithm, the Dannenbring rapid access with extensive search algorithm, and a mixed integer linear programming procedure.The problem factors considered in this study were number of jobs, number of machines, and range of processing times. Relatively small-sized problems were tested with up to ten jobs, five machines, and 1–100 processing time units. Six solution techniques were selected and compared, with respect to makespan and computational time requirements, for multiple combinations of the three problem variables.The resulting test data were investigated using graphical procedures and formal statistical analyses. Initially, plots of mean values were used to graphically compare the six solution methods for the two performance criteria. Next, a multivariate analysis of variance study was conducted to investigate the quality and efficiency of the algorithms with respect to the problem factors. Then, a multiple comparison procedure was employed to analyze treatment mean differences among the six solution techniques. Results from the statistical analyses are summarized in this article.It was concluded that the two mathematical programming methods, the integer linear programming procedure and the mixed integer linear programming methods, produced the best performance in terms of makespan. These two methods, however, used a far greater amount of computational time than the other four solution techniques. Producing moderately good results as far as quality of performance, the Gupta and the Szwarc algorithms were comparable with the Campbell et al. and the Dannenbring algorithms in terms of computational efficiency. By comparison, the Campbell et al. and the Dannenbring algorithms produced the poorest performance with respect to the quality of solutions.Certain limitations were imposed for this study. The problem size considered was relatively small and the sample size was also limited to ten problems per cell. In addition, a uniform distribution function was used for generating processing times within certain ranges. These limitations were necessary in order to allow the various scheduling problems to be solved within a reasonable amount of computer time.Finally, some suggestions were provided for future research in the NIS problem area. The integer linear programming method was recommended as a standard of evaluation, owing to its best overall performance. A possible area for future research would involve the improvement of the Gupta and the Szwarc algorithms through the use of backtracking procedures within the branch-and-bound technique, so that they might be competitive with the mathematical programming methods with respect to quality of performance. Other distribution functions could be investigated in terms of the influence of the distribution of processing times on the performance measures.     

生产企业合同交货期确定及合同排序

讨论了企业订货合同管理中面临的决策问题以及解决途径。应用机器工件调度理论求解包括提前和延期惩罚的合同排序问题，给出了启发式排序规则和求解搜索策略。采用了3种启发式方法：1）接排序规则排序；2）对初始排序施加成对交换技术改善；3）射束搜索技术。实验结果表明，第3种求解质量具有明显优势，能得到令人满意的结果。     

启发式方法确定最短配送路径

描述配送中心最短配送路径的数学模型并提出应用基于模拟退火的启发式方法求解，同时详细说明了该方法中问题解的表示方法、产生新解的方法以及优化方法流程，并对该方法的可行性和有效性进行验证。     

A parallel insertion heuristic for vehicle routing with side constraints

In the early eighties, Fisher and Jaikumar developed a generalized assignment heuristic for vehicle routing problems. In this paper, we discuss some of the strong and weak points of this heuristic, and take its basic ideas to develop a new parallel insertion heuristic for the vehicle routing and scheduling problem that is better able to handle various side constraints.     

Scheduling independent jobs on nonuniform, unequal processors

The problem of scheduling n independent jobs on a single processor to minimize the total tardiness of the assignment has attracted much attention. Solution algorithms, both exact and approximate, have been reported, but no polynomial time exact algorithm has yet been found, nor has the problem been proven NP-complete.In this paper we consider the more general case of scheduling n independent jobs on m unequal processors to minimize total tardiness. Since this problem is more complex than the corresponding single-processor problem, no polynomial-time algorithm is in sight. For problems of this nature, approximate algorithms may be more valuable than exact algorithms in terms of applications. A heuristic algorithm is developed to solve the multiple-processor problem. Computational experiments show that the heuristic algorithm is efficient, fast, and easy to implement.     

Transportation cost changes with statewide school district consolidation

This article studies the relationship between school district size and bus transportation costs, and estimates the change in such costs when a statewide policy of consolidation is pursued. To explore this relationship, we develop a multiple-objective model and solution procedure that combines a geographic aggregation and bus routing heuristic to generate consolidation scenarios. The heuristic was developed to explicitly consider efficiency, effectiveness, and equity objectives, and can be applied in both urban and rural states. The scenarios will generate average statewide bus transportation costs. As applied to the State of Iowa, within the legislature's proposed range of consolidation of 500-1000 students, it was found that transportation operational and capital cost increases range from 0.6 to 10.6 percent and 0.7 to 7.7 percent, respectively.     

How effective are heuristic solutions for electricity planning in developing countries

Heuristic algorithms have been widely used to provide computationally feasible means of exploring the cost effective balance between grid versus off grid sources for universal electrification in developing countries. By definition in such algorithms however, global optimality is not guaranteed. We present a computationally intensive but globally optimal mixed integer non-linear programming (MINLP) model for electricity planning and use it in a Monte Carlo simulation procedure to test the relative performance of a widely used heuristic algorithm due to [28]. We show that the overall difference in cost is typically small suggesting that the heuristic algorithm is generally cost effective in many situations. However we find that the relative performance of the heuristic algorithm deteriorates with increasing degree of spatial dispersion of unelectrified settlements, as well as increasing spatial remoteness of the settlements from the grid network, suggesting that the effectiveness of the heuristic algorithm is context specific. Further, we find that allocation of off grid sources in the heuristic algorithm solution is often significantly greater than in the MINLP model suggesting that heuristic methods can overstate the role of off-grid solutions in certain situations.     

卷烟厂制丝车间自动排产问题研究

以卷烟厂为研究背景,对制丝车间生产特点和排产需求进行分析,提出了基于规则的启发式算法,以解决卷烟厂制丝车间排产问题。以生产均衡为目标,构建以工段为整体的倒序排产的制丝车间排产算法,并将该算法应用于某卷烟厂。经实际数据验证,该算法可很好地满足制丝排产的需求。     

A cost evaluation method for dynamic line balancing

A procedure is presented for calculating stochastic costs, which include operator (labor) and inventory costs, associated with dynamic line balancing. Dynamic line balancing, unlike the traditional methods of assembly and production line balancing, assigns operators to one or more operations, where each operation has a predetermined processing time and is defined as a group of identical parallel stations. Operator costs and inventory costs are stochastic because they are functions of the assignment process employed in balancing the line, which may vary throughout the balancing period, and the required flow rate. Earlier studies focused on the calculation of the required number of stations and demonstrated why the initial and final inventories at the different operations are balanced.The cost minimization method developed in the article can be used to evaluate and compare the assignment of operators to stations for various assignment heuristics. Operator costs and inventory costs are the components of the cost function. The operator costs are based on the operations to which operators are assigned and are calculated for the entire work week regardless of whether an operator is given only a partial assignment which results in idle time. It is assumed that there is no variation in station speeds, no learning curve effect for operators' performance times, and no limit on the number of operators available for assignment. The costs associated with work-in-process inventories are computed on a “value added” basis. There is no charge for finished goods inventory after the last operation or raw material before the first operation.The conditions which must be examined before using the cost evaluation method are yield, input requirements, operator requirements, scheduling requirements and output requirements. Yield reflects the output of good units at any operation. The input requirement accounts for units discarded or in need of reworking. The operator requirements define the calculation of operator-hours per hour, set the minimum number of operators at an operation, and require that the work is completed. The scheduling requirements ensure that operators are either working or idle at all times, and that no operator is assigned to more than one operation at any time. The calculation of the output reflects the yield, station speed, and work assignments at the last operation on the line.An application of the cost evaluation method is discussed in the final section of the article. Using a simple heuristic to assign operators, the conditions for yield, inputs, operators, scheduling, and output are satisfied. The costs are then calculated for operators and inventories.In conclusion, the cost evaluation method for dynamic balancing enables a manager to compare the costs of assigning operators to work stations. Using this method to calculate the operator and inventory costs, a number of different heuristics for assigning operators in dynamic balancing can be evaluated and compared for various configurations of the production line. The least cost solution procedure then can be applied to a real manufacturing situation with similar characteristics.     

The trade-off between the net present cost of a project and the probability to complete it on schedule

In this article we consider the probability of not completing a project on schedule (or the risk of delays) and its effect on the net present cost of the project. We propose an efficient frontier that points out to management the trade-off between low risk, early start schedules and high risk, late start schedules. Early start schedules minimize the risk of delays at the cost of early investment in project activities and material. Late start schedules delay capital outlays while increasing the risk of not completing the project on its due date.The methodology developed in this study is aimed at strategic level decision making. At this level, decisions are based on incomplete information that calls for stochastic analysis and the introduction of uncertainty. Uncertainty in project management is introduced through stochastic activity duration and stochastic lead times of resources required for the project. The commonly used CPM analysis ignores those aspects of uncertainty. PERT analysis does consider the stochastic nature of activity durations but computes only the probability to complete the project on a given date for a single schedule.A crucial decision at the strategic level of project management is when to schedule activities with high value-added. The decision makers have to trade-off the advantages of delaying such activities, thus reducing the net present cost of the project, with the disadvantages associated with increasing the probability of not completing the project on time.The number of feasible schedules in a real project is typically large and exact analysis of all possible schedules is difficult to perform, if not impossible. This article presents a heuristic procedure that generates an efficient frontier representing the risk of delays versus the net present cost of the project. The efficient frontier is a decision aid for the manager who has to choose the appropriate schedule for the project.Most computer packages for project management are based on CPM (especially packages for personal computers). Our heuristic procedure is designed to be used as an extension to CPM analysis. The procedure starts with the early start schedule developed by CPM and, using the computed slacks, tries to delay activities with high value-added one at a time. At each iteration a Monte-Carlo-type simulation is used to approximate the probability of not completing the project on time. This probability is stored along with the net present cost of the project. The result of the analysis is a set of points on the plane representing the probability of not completing the project on time versus the net present cost of the project. Each point corresponds to a specific schedule. Management can choose the most appropriate schedule for implementation based on its attitude towards risk and its financial policy.A simple example is used to illustrate the heuristic procedure. In the example, a project with six activities and two types of resources is analyzed. Five schedules are generated with net present cost ranging from $45,000 to $8,191,000 and the probability of not completing the project on time ranging from 0.0001 to 0.75. Our experience with a real project of 400 activities is reported as well.The heuristic procedure can be implemented easily on advanced “Fourth Generation” packages for project management such as IBM's Application System (AS) or Metier's Artemis system. The heuristic procedure can also be implemented on personal computers by processing the output of any CPM package by the special subroutine that is developed in this study.     

基于动态约束的炼钢连铸重调度算法设计

针对炼钢连铸过程中出现的新炉次插入的重调度问题,考虑实际生产中的工艺约束,以最小化开工时间差异度、加工机器差异度的加权和为目标函数建立动态调度模型,采用回溯算法与启发式规则结合的算法。用Matlab7.8.0软件对选取的算例进行仿真,结果表明,此算法能保证重调度结果的实时性和有效性。     

Personnel scheduling with flexshift models

The concept of personnel scheduling when alternative work hours are permitted is presented in this article. The concept, called Flexshifts, schedules 6-, 8-, and 10-hour shifts against a 12- and 24-hour daily demand profile. Using the concept, required shifts can then be offered to the labor staff allowing each individual to select those shifts that best fit their personal plans. Alternatively, certain shifts can be guaranteed to key employees. Case studies reported in this paper indicate many advantages to allowing workers to opt for different start times, to select their days off and to create non-standard workweeks from predefined sets of 6-, 8-, and 10-hour days. Computerized timekeeping systems make this flexibility manageable. Personnel scheduling algorithms such as the one presented here make the planning of Flexshift easy.The formulation presented here utilizes linear programming. Tests of the L.P. Flexshift model on 42 data sets of 12-hour days showed an average savings in labor of 24.2% when compared to an L. P. model of the traditional 8-hour work shift. For a 24-hour work pattern, that formulation outperformed a published heuristic for 8-hour shifts by reducing average idle time from 13.9 to 5.4%.     

Scheduling and resource allocation in a food service system

The scheduling of food production is often accomplished informally based upon approximate time requirements stated in recipes and the judgment and experience of a food production manager, administrative dietician, or cook. Such schedules are seldom optimized to least overall duration and consequently contain periods of non-productive time on the part of personnel and resources. In addition, these schedules often attempt to avoid resource conflicts through the early scheduled completion of work activity; this leads to many of the menu items being completed sufficiently in advance of serving time that undesirable changes in the nutritional, organoleptic and microbiological properties of the food can take place.In this paper, a branch and bound algorithm is presented as a solution procedure for the foodservice scheduling problem. The advantage of branch and bound in comparison to a heuristic based scheduling procedure is that it can produce schedules which are optimized to least overall duration from start to finish. The added computational cost of the branch and bound procedure is justified, because most foodservice systems cycle their menus. Consequently, each of a finite number of schedules is reused numerous times over an extended period resulting in long-term productivity gains.Another advantage of the algorithm is that right-shifted or late start schedules may be produced. This is in keeping with our objective of minimizing the delay time between the completion of the food and its being served to the consumer.The paper describes a method by which the process time for each of the various steps in a recipe may be computed as a function of the number of servings being prepared. Although these are normally considered to be linear relationships, the algorithm can easily be modified to accept other types of relationships as well.Perhaps the most important aspect of the this research is that the branch and bound algorithm has been implemented to perform branching operations over two classes of decisions. The first class of decisions involves the selection of which recipe steps or activities are to be scheduled at a certain time, and the second class of decisions involves the choice of which resource class to assign to the activities in those cases where alternative resources are allowed. This dual branching philosophy provides a great deal of flexibility to the decision maker for handling the type of scheduling problems commonly found in practice. The expense of this added flexibility, however, is a substantial increase in the size of the decision tree which must be developed and explored.In order to demonstrate the performance of the algorithm for practical purposes, the lunch menus of a short term, acute case, 300 bed hospital in Syracuse, New York were used to develop production schedules. These menus included a total of 89 different hot food items whose recipes were placed into a menu file in the computer along with the coefficients needed to develop process time estimates as a function of numbers of servings to be prepared. In total, fourteen lunch menus are cycled at the hospital; the number of items appearing on the menus ranges from 8 to 14 hot food items.In the first series of tests, resources were assumed not to be interchangeable. The branch and bound procedure was successful in producing optimal solutions for eleven of the fourteen schedules. The three menus which were not optimally solved were aborted, because the size of the solutions tree grew beyond that which could be stored in 500K bytes of common memory. In spite of this, however, the upper bound solutions given by the aborted problems were found to be very close to lower bound values and therefore may be considered as very good solutions.In the second series of tests, certain resources were allowed to be interchangeable for some of the activities. Specifically, we assumed two labor classes. The first of these are called special cooks who are more experienced personnel. Normally special cooks prepare entree items, but they may be called upon in some cases to perform any activity normally performed by the second labor class- the less experienced cooks—who normally prepare soups, sauces and vegetables. The cooks, on the other hand, are never allowed to prepare menu items which call for special cooks. These groundrules are identical to those currently in practice at the hospital from which the test problems were obtained. Ten of the fourteen menus were selected for this series of tests. In all of the ten cases, the algorithm successfully developed optimal solutions without exceeding the 500K byte common memory limitation. And, in spite of the vastly increased tree size resulting from the dual decision branches, the computation times for these tests were only modestly greater than those of the first set of tests where alternative resources were not considered. The success of the algorithm in solving the dual decision problems resulted in large part from its ability to develop strong upper bounds very early in solution process. In addition, the characteristics of food production scheduling problems are such that the lower bound pruning is very effective especially in the early stages of tree development.It is important to note that the use of an algorithm such as this in a practical setting affords a very friendly user interface. Once the foodservice system's menu items have been placed into a file, the user may easily select any set of these items to include in a given schedule. Only three lines of data input are required. The first line specifies the number of items as well as the zero-hour or serving time. The second line identifies the item numbers of the hot-food items to be scheduled. And the third line specifies the number of servings for each of those items which must be prepared. Kitchen personnel with limited experience can be trained to input the data in less than 15 minutes of instruction time.     

Scheduling of re-entrant flow shops

We propose and develop a scheduling system for a very special type of flow shop. This flow shop processes a variety of jobs that are identical from a processing point of view. All jobs have the same routing over the facilities of the shop and require the same amount of processing time at each facility. Individual jobs, though, may differ since they may have different tasks performed upon them at a particular facility. Examples of such shops are flexible machining systems and integrated circuit fabrication processes. In a flexible machining system, all jobs may have the same routing over the facilities, but the actual tasks performed may differ; for instance, a drilling operation may vary in the placement or size of the holes. Similarly, for integrated circuit manufacturing, although all jobs may follow the same routing, the jobs will be differentiated at the photolithographic operations. The photolitho-graphic process establishes patterns upon the silicon wafers where the patterns differ according to the mask that is used.The flow shop that we consider has another important feature, namely the job routing is such that a job may return one or more times to any facility. We say that when a job returns to a facility it reenters the flow at that facility, and consequently we call the shop a re-entrant flow shop. In integrated circuit manufacturing, a particular integrated circuit will return several times to the photolithographic process in order to place several layers of patterns on the wafer. Similarly, in a flexible machining system, a job may have to return to a particular station several times for additional metal-cutting operations.These re-entrant flow shops are usually operated and scheduled as general job shops, ignoring the inherent structure of the shop flow. Viewing such shops as job shops means using myopic scheduling rules to sequence jobs at each facility and usually requires large queues of work-in-process inventory in order to maintain high facility utilization, but at the expense of long throughput times.In this paper we develop a cyclic scheduling method that takes advantage of the flow character of the process. The cycle period is the inverse of the desired production rate (jobs per day). The cyclic schedule is predicated upon the requirement that during each cycle the shop should perform all of the tasks required to complete a job, although possibly on different jobs. In other words, during a cycle period we require each facility to do each task assigned to it exactly once. With this requirement, a cyclic schedule is just the sequencing and timing on each facility of all of the tasks that that facility must perform during each cycle period. This cyclic schedule is to be repeated by each facility each cycle period. The determination of the best cyclic schedule is a very difficult combinatorial optimization problem that we cannot solve optimally for actual operations. Rather, we present a computerized heuristic procedure that seems very effective at producing good schedules. We have found that the throughput time of these schedules is much less than that achievable with myopic sequencing rules as used in a job shop. We are attempting to implement the scheduling system at an integrated circuit fabrication facility.     

A heuristic rule for routing customers to parallel servers

A practically important problem is the assignment of stochastically arriving service requests to one of several parallel service groups so as to minimize the long-run average sojourn time per service request. An exact solution of this multi-dimensional optimization problem is computationally infeasible. A simple heuristic solution method yielding a good suboptimal rule will be given for the case of server groups with different and generally distributed service times. This solution method is based on a decomposition approach and first principles from Markov decision theory. The main idea of the heuristic method is to apply one step of policy improvement to the best Bernoulli-splitting rule.