A FRAMEWORK FOR MACHINE SCHEDULING PROBLEMS WITH CONTROLLABLE PROCESSING TIMES

This is a study of single and parallel machine scheduling problems with controllable processing time for each job. The processing time for job j depends on the position of the job in the schedule and is a function of the number of resource units allocated to its processing. Processing time functions and processing cost functions are allowed to be nonlinear. The scheduling problems considered here have important applications in industry and include many of the existing scheduling models as special cases. For the single machine problem, the objective is minimization of total compression costs plus a scheduling measure. The scheduling measures include makespan, total flow time, total differences in completion times, total differences in waiting times, and total earliness and tardiness with a common due date for all jobs. Except when the total earliness and tardiness measure is involved, each case the problem is solved efficiently. Under an assumption typically satisfied in just-in-time systems, the problem with total earliness and tardiness measure is also solved efficiently. Finally, for a large class of processing time functions; parallel machine problems with total flow time and total earliness and tardiness measures are solved efficiently. In each case we reduce the problem to a transportation problem.     

SCHEDULING HYBRID FLOWSHOPS IN PRINTED CIRCUIT BOARD ASSEMBLY LINES*

We treat a three‐stage hybrid flowshop for the production of printed circuit boards (PCB), suggested to us by a real‐life production situation. The problem is to determine a schedule that minimizes the makespan for a given demand profile over a finite planning horizon. We propose a global procedure that utilizes genetic algorithms and three subproblems. The performance of the procedure is evaluated via experimentation over thousands of problem realizations that are randomly generated. The experimental results show the efficiency of the global procedure and provides qualitative answers to the allocation of machines to the various stages.     

PRACTICE‐FOCUSED RESEARCH ISSUES FOR SCHEDULING SYSTEMS*

Scheduling research has had relatively little impact on manufacturing practice, yet within the last several years, there has been an explosive growth in the development and implementation of computer‐based scheduling systems in industry. Changes in the environment have increased the stakes and the opportunities for the results of scheduling research to influence manufacturing competitiveness. This paper draws on field‐related experiences with the development and implementation of scheduling systems to propose high‐impact research topics.     

A COMPARISON OF ORDER-RELEASE AND DISPATCH RULES FOR THE DYNAMIC WEIGHTED EARLY/TARDY PROBLEM

The early/tardy problem is one of the most vexing pieces of the complex production scheduling decision process. So far most of the research has been on single-machine environments. Hence, we considered the weighted early/tardy scheduling problem in a simulated dynamic multimachine job shop. We analyzed controlled job-release and dispatch rules using time and cost information at a variety of stationary and nonstationary utilization rates, due-date allowances, and early/tardy cost levels. We found a newly developed method for controlling the release for all job operations using early/tardy cost information, superior to other release mechanisms overall in both our stationary and nonstationary analyses. We found immediate release useful at many high utilization conditions and a gateway-only release method best in many low utilization conditions. A modified version of a single-machine early/tardy dispatch method was clearly superior to the dispatch rules for almost all the simulated shop conditions.     

A SINGLE-MACHINE SCHEDULING MODEL WITH FIXED-INTERVAL DELIVERIES

We consider an environment where a production facility modeled as a single machine needs to assign delivery dates to several orders and find a feasible sequence. Tardy jobs are not allowed. The delivery dates are to be at prespecified fixed intervals. The objective is to minimize the due date penalty and the cost of earliness. We provide a dynamic programming-based solution procedure that runs in polynomial time. We develop several dominance results that reduced the computational requirement by an order of magnitude in our computational study.     

A MODEL-BASED DECISION SUPPORT SYSTEM FOR SCHEDULING LUMBER DRYING OPERATIONS

Raw lumber must be dried to a specified level of moisture content before it can be used to make furniture. This paper deals with a model-based decision support system (DSS) for a local furniture manufacturing company to assist its management in scheduling lumber drying operations. In addition to buying ready-to-use dried lumber from vendors at a premium, the company processes raw lumber in house using two production process that require various lengths of processing time in predryers and dry-kilns. Given the demand for various types of dried lumber over a specified planning horizon, the processing times and costs for each production process, technological restrictions, and management policies, the problem of interest is to satisfy the demand at a minimum cost. The DSS incorporates the mathematical formulation of this problem, is user friendly, maintains model and data independence, and generates the necessary reports, including loading and unloading schedules for the equipment.     

JOB RELEASE CONTROL USING A CYCLIC SCHEDULE*

In just‐in‐time inventory management in any manufacturing setting, the general idea has been to release jobs as late as possible (to reduce inventory costs) while still having them arrive at bottleneck machines in time to maintain the desired throughput (by not starving a bottleneck machine). When a cyclic schedule is employed, the throughput is determined by a cyclic sequence of operations known as the cyclic critical path. These operations are not, in general, all performed on a single bottleneck machine. We present an algorithm for releasing jobs that treats this cyclic critical path as the bottleneck. Although this algorithm has the somewhat complex task of not delaying any of these operations on the cyclic critical path, it is greatly simplified by being able to take advantage of the fixed sequence of the cyclic schedule. The result is that the algorithm is relatively simple to implement. Although it uses a simulation‐based analysis, this analysis can all be done and the necessary results stored in advance of its use. We test the algorithm in a job shop environment with stochastic operation times. This algorithm is shown to be effective at reducing inventory while avoiding decreases in throughput.     

AN ANALYSIS AND DISCUSSION OF THE OPTIMIZED PRODUCTION TECHNOLOGY SOFTWARE AND ITS USE

During the 19805 much attention, both pro and con, was directed toward optimized production technology (OPT). Criticism was directed at the proprietary nature of the scheduling algorithms within the software. Despite these criticisms, many large companies installed OPT. Little has been written on how the software is constructed and operates. This article introduces the software, provides a discussion of how it interfaces with management, and how various algorithms are imbedded in the software function. Last, a survey of companies that had implemented the software revealed that the major users are in the automotive industry.     

LOGISTICS MANAGEMENT SYSTEM: AN ADVANCED DECISION SUPPORT SYSTEM FOR THE FOURTH DECISION TIER DISPATCH OR SHORT-INTERVAL SCHEDULING

The Logistics Management System (LMS) is a real-time transaction-based system combining decision technologies from AI, MS/OR, and decision support system that serves very successfully as a dispatcher or short-interval scheduler by monitoring and controlling the manufacturing flow of IBM's semiconductor facility near Burlington, Vermont. LMS coordinates the actions and decisions of several logically isolated participants in a serially dependent system of activities. Therefore, it balances the requirements of several goals (cycle time, output, serviceability, and inventory management) that compete for the same resource, exploits emerging opportunities on the manufacturing floor, and reduces the distortion from unplanned events. This paper provides an overview of the LMS application, the concept of interrelated decision tiers in manufacturing decision making, and the need for the dispatch decision tier to successfully reduce apparent randomness. Historically, production and operations management has ignored this decision tier. This has significantly limited our ability to make an impact on the performance of the manufacturing operation.