A Primal-dual Steepest-edge Method for Even-flow Harvest Scheduling Problems

The even-flow harvest scheduling problem arises when the forestry agency has evolved into a rigid non-declining even-flow policy. In this paper, we investigate model formulation and solution strategies for the even-flow harvest scheduling problem. A multiple-objective linear programming problem is formulated for even-flow harvest scheduling problems with multiple-site classes and multiple periods. The aim of this problem is to simultaneously maximize a desired harvest-volume per hectare for each period of planning horizon and the total economic return. A block diagonal constraint structure, with many sets of network sub-problems and a set of coupling constraints, is identified in this linear programming problem. A longest path method for each of network sub-problems and a primal-dual steepest-edge algorithm for the entire problem are developed. The developed algorithm has been coded in Borland C++ and implemented on a personal computer. An illustrative example is used to display the detailed procedure for the developed algorithm and a real-world case study is used to show the trade-off between desired even-flow harvest volume policy and total economic return. Results show the potential benefits of this approach.     

An efficient heuristic for scheduling batches of parts in a flexible flow system

Flexible manufacturing systems (FMSs) are a class of automated systems that can be used to improve productivity in batch manufacturing. Four stages of decision making have been defined for an FMS—the design, planning, scheduling, and control stages. This research focuses on the planning stage, and specifically in the area of scheduling batches of parts through the system.The literature to date on the FMS planning stage has mostly focused on the machine grouping, tool loading, and parttype selection problems. Our research carries the literature a step further by addressing the problem of scheduling batches of parts. Due to the use of serial-access material-handling systems in many FMSs, the batch-scheduling problem is modeled for a flexible flow system (FFS). This model explicitly accounts for setup times between batches that are dependent on their processing sequence.A heuristic procedure is developed for this batch-scheduling problem—the Maximum Savings (MS) heuristic. The MS heuristic is based upon the savings in time associated with a particular sequence and selecting the one with the maximum savings. It uses a two-phase method, with the savings being calculated in phase I, while a branch-and-bound procedure is employed to seek the best heuristic solution in phase II. Extensive computational results are provided for a wide variety of problems. The results show that the MS heuristic provides good-quality solutions.     

Scheduling in or-parallel Prolog systems: Survey and open problems

Implementation of or-parallel Prolog systems offers a number of interesting scheduling problems. The main issues are the interaction between memory models and scheduling, ordering of multiple solutions, and scheduling of speculative work. The problems occur partly because of the design choices (e.g. the choice of a memory model), and partly because of the desire to maintain observational equivalence between parallel and sequential implementations of Prolog, while achieving high efficiency. In the first part of this paper a common framework for discussing scheduling in or-parallel systems is introduced, and also a collection of issues that must be addressed in such systems is presented. In the second part of the paper we survey a number of solutions to these problems comparing their efficiency whenever possible. We close the survey with a short discussion of open problems.Current association: Carlstedt Elektronik AB     

Hierarchical production control for a flow shop with dynamic setup changes and random machine breakdowns

In this paper, we study a manufacturing system consisting of two machines separated by two intermediate buffers, and capable of producing two different products. Each product requires a constant processing time on each of the machines. Each machine requires a constant non-negligible setup change time from one product to the other. The demand rate for each product is considered to be piecewise constant. Each machine undergoes failure and repair. The time-to-failure and time-to-repair are exponentially distributed random variables. The setup change and processing operations are resumable. We model our system as a continuous time, continuous flow process. An optimal control problem is formulated for the system to minimize the total expected discounted cost over an infinite horizon. To determine the optimal control policy structure, a discrete version of the problem is solved numerically using a dynamic programming formulation with a piecewise linear penalty function. A real-time control algorithm is then developed with the objective of maintaining low work-in-process inventory and keeping the production close to the demand. The algorithm uses a hierarchical control structure to generate the loading times for each product on each machine in real time and to respond to random disruptions in the system. The system is simulated using this algorithm to study its performance. The performance of the algorithm is also compared to alternative policies.     

A multi-objective programming model for scheduling emergency medicine residents

Scheduling emergency medicine residents (EMRs) is a complex task, which considers a large number of rules (often conflicting) related to various aspects such as limits on the number of consecutive work hours, number of day and night shifts that should be worked by each resident, resident staffing requirements according to seniority levels for the day and night shifts, restrictions on the number of consecutive day and night shifts assigned, vacation periods, weekend off requests, and fair distribution of responsibilities among the residents. Emergency rooms (ERs) are stressful workplaces, and in addition shift work is well-known to be more demanding than regular daytime work. For this reason, preparing schedules that suit the working rules for EMRs is especially important for reducing the negative impact on shift workers physiologically, psychologically, and socially. In this paper, we present a goal programming (GP) model that accommodates both hard and soft constraints for a monthly planning horizon. The hard constraints should be adhered to strictly, whereas the soft constraints can be violated when necessary. The relative importance values of the soft constraints have been computed by the analytical hierarchy process (AHP), which are used as coefficients of the deviations from the soft constraints in the objective function. The model has been tested in the ER of a major local university hospital. The main conclusions of the study are that problems of realistic size can be solved quickly and the generated schedules have very high qualities compared to the manually prepared schedules, which require a lot of effort and time from the chief resident who is responsible for this duty.     

A decision-making approach to the operation of flexible manufacturing systems

This paper introduces a generic decision-making framework for assigning resources of a manufacturing system to production tasks. Resources are broadly defined production units, such as machines, human operators, or material handling vehicles; and tasks are activities performed by resources. In the specific context of FMS, resources correspond to individual machines; tasks correspond to operations to be performed on parts. The framework assumes a hierarchical structure of the system and calls for the execution of four consecutive steps to make a decision for the assignment of a resource to a task. These steps are 1) establishment of decision-making criteria, 2) formation of alternative assignments, 3) estimation of the consequences of the assignments, and 4) selection of the best alternative assignment. This framework has been applied to an existing FMS as an operational policy that decides what task will be executed on which resource of this FMS. Simulation runs provide some initial results of the application of this policy. It is shown that the policy provides flexibility in terms of system performance and computational effort.     

Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions

A variant of the High Multiplicity Multiprocessor Scheduling Problem with C job lengths is considered, in which jobs can be processed only by machines not greater than a given index. When C=2, polynomial algorithms are proposed, for the feasibility version of the problem and for maximizing the number of scheduled jobs.     

Integration of batching and scheduling for hot rolling production in the steel industry

This paper investigates the hot rolling production scheduling problem in the steel industry and proposes a new mixed integer programming model for this problem based on the monolithic modeling strategy that integrates batching and scheduling. Using this strategy, the new model can simultaneously schedule multiple turns and simultaneously determine the production timetable of these turns in a global optimal view. A long-term tabu search heuristic using frequency-based memory is developed to obtain near-optimal solutions for this problem. Three kinds of speed-up strategies are developed to accelerate the search procedure of the proposed tabu search. A practical scheduling system combining the proposed mathematical model and the tabu search heuristic has been developed and tested on instances collected from practical production data. The experimental results show that the proposed mathematical model and the tabu search heuristic outperform both the current manual scheduling method and the traditional serial method.