Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach

In today's fast-paced Just-In-Time and mass customization manufacturing in a sequence-dependent setup environment, the challenge of making production schedules to meet due-date requirements is becoming a more complex problem. Unfortunately, much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of minimizing tardiness, a common measure of due-date performance, in a sequence-dependent setup environment. Simulated annealing was used to solve the sequencing problem, and its performance was compared with random search. Our experimental results show that the algorithm can find a good solution fairly quickly, and thus can rework schedules frequently to react to variations in the schedule. The algorithm is invaluable for ‘on-line’ production scheduling and ‘last-minute’ changes to production schedule. The results of this research also suggest ways in which more complex and realistic job shop environments, such as multiple machines with a higher number of jobs in the sequence, and other scheduling objectives can be modeled. This research also investigates computational aspects of simulated annealing in solving complex scheduling problems.     

SCHEDULING JOBS ON PARALLEL PROCESSORS WITH DYNAMIC PROGRAMMING

The problem of scheduling jobs on M-parallel processors is one of selecting a set of jobs to be processed from a set of available jobs in order to maximize profit. This problem is examined and a dynamic programming solution is presented which decomposes it into a sequencing problem within an allocation problem. The computation required for solution is found to depend on the sequencing problem as it is affected by the waiting cost function. Various forms of the waiting cost function are considered. The solution procedure is illustrated by an example, and possible extensions of the formulation are discussed.     

Hospital resident scheduling problem

This paper addresses the resident scheduling problem (RSP) at hospitals concerned with prescribing work-nights for residents while considering departmental staffing and skill requirements as well as residents' preferences. Three scenarios that represent most situations and account for various departmental requirements and needs are described. Although similar scheduling problems are considered in the literature, no analysis exists that adequately deals with the speciffic nature of this problem. The problem is modeled as a mixed-integer program and heuristic solution procedures are developed for the different identified scheduling scenarios. These procedures exploit the inherent network structure of the problem which is an important feature that enhances problem solvability. For the sake of comparison, the problem is also solved exactly via the CPLEX-MIP (version 6.0) package. The contribution of this work is important since many hospitals are still utilizing manual techniques in preparing their own schedules, expending considerable effort and time and yet contending with limited scheduling flexibility.     

Master Scheduling in Assemble-To-Order Environments: A Capacitated Multiobjective Lot-Sizing Model

Basic characteristics of an assemble-to-order environment make effective master scheduling extremely difficult. Limited resource capacities and dynamic customer end-item demand contribute to the complexity of the master production scheduling problem. To gain flexibility and responsiveness within this system, the master production schedule (MPS) focuses at the component level. This research proposes a master scheduling technique for manufactured components which combines a multiobjective capacitated multi-item/multi-stage lot-sizing model with an interactive multiple objective optimization solution procedure. To evaluate the model's performance as a realistic and practical master scheduling tool, this study focuses on the National Cash Register (NCR) electronics manufacturing facility in Columbia, South Carolina.     

Integrative Cycle Scheduling Approach for a Capacitated Flexible Assembly System*

This study revisits the traditional single stage, multi-item, capacitated lot-sizing problem (CLSP) with a new integrative focus on problem structuring. Unlike past research, we develop integrative cycle scheduling approaches which simultaneously address lot-sizing, capacity, and sequencing issues. Our purposes are to (1) explore the effect of sequencing on inventory levels, (2) examine the problem of infeasibility in the economic lot scheduling problem (ELSP), and (3) provide a simple methodology of generating low-cost cycle schedules in an environment with discrete shipping, dynamic demands, limited capacity, zero setup cost, and sequence-independent setup times. Our procedures are compared to benchmark cycle scheduling approaches in terms of both inventory cost and computation time under different demand scenarios, using the operating data from a flexible assembly system (FAS) at the Ford Motor Company's Sandusky, Ohio plant.     

A new prototype system for optimized job shop scheduling

Optimal scheduling of shopfloor activities in an environment of discrete part manufacturing is discussed. The scheduling problem is a well known NP complete one. The main part, the sequencing problem, has been tackled using two techniques: virtual resources identification and taboo search heuristics. The first approach allowed the authors to reduce the complexity of the sequencing from a job shop to a general flow shop problem. On the other hand, the search for an optimal solution, with respect to a fixed strategy, has been achieved via the taboo search. A synthesis of the results of a large number of tests is presented as well as the results of an application to a real case. The latter is shown in comparison with the output of the system being presently used in the examined factory.     

考虑交货因素的热轧无缝钢管订单排程模型与算法

无缝钢管的市场需求具有多品种、小批量的特点，为了在满足客户需求的同时保证高效连续化生产，文章在满足生产工艺特征的基础上将配送地址和交货期等合同因素引入热轧无缝钢管订单排程问题中，建立了以适期交货、订单集中生产配送和最小化机器设备调整为优化目标的订单排程优化模型，并设计了两阶段求解算法：首先，以订单交货期与配送地址差异最小为目标，基于凝聚策略设计了订单聚类算法，将具有相同工艺约束、相似合同要求的订单进行聚类，并形成初始轧制计划；然后，以设备调整和提前/拖期最小为目标，设计混合变邻域搜索算法，对初始轧制批次进行排程优化。基于实际订单数据的实验结果表明，模型和算法对问题的描述和求解是可行有效的。     

Parallel machine scheduling subject to auxiliary resource constraints

This paper is motivated by scheduling photolithography machines in semiconductor manufacturing wherein reticle requirements are the auxiliary resource constraints. As the problem is NP hard, two different heuristic solution approaches are developed. The performance of our network-based mathematical model and heuristics are evaluated through an extensive set of problem instances. The best performing heuristic method typically produces solutions that are 1.72% above optimal. If this method is used as the seed solution for a Tabu search-based post processing algorithm, schedules that are 0.78% above the optimal solution, on average, are possible.     

A mathematical model for job shop scheduling with multiple process plan consideration per job

In this paper, a mixed integer programming model is formulated for scheduling a set of jobs through a shop when each job is supplied or provided with multiple process plans or process routings. Simultaneous selection of a process plan for each job and the sequencing of the jobs through the machines in the shop based on the set of selected process plans is addressed. The procedure developed seeks to integrate the selection of machines for each job and the sequencing of jobs on each machine based on the objective of minimizing production makespan. the application of the procedure is demonstrated with an example problem. The following conclusions were drawn as a result of the research: (1) the procedure developed produces optimal or near optimal solution; (2) the benefit from the developed approach is that it allows a shop to adaptively select process plans for jobs to optimize on production makespan. By combining solution quality with scheduling flexibility and efficiency, the productivity of a shop can be greatly enhanced.     

A UNIVERSITY EXAMINATION-SCHEDULING MODEL TO MINIMIZE MULTIPLE-EXAMINATION DAYS FOR STUDENTS

Scheduling university examinations is often done with the objective of spreading a student's required examinations over an examination week. That is the equivalent of the problem of minimizing the number of examinations a student must take on any one day. An approach to scheduling exams which relates the problem to the classical assignment problem is discussed. The model developed is a symmetry-constrained assignment model, and the solution method requires use of a branch-and-bound algorithm. Results from application of the algorithm to six semesters of actual data are presented.     

An efficient scheduling algorithm for the hot coil making in the steel mini-mill

This paper investigates and suggests an efficient solution to the problem of scheduling the steel making line in the Mini Steel Mill, which consists of three major processes: molten steel making, continuous slab casting, and hot charged rolling. Careful synchronization of these processes is a key productivity factor, since a very limited amount of work-in-process inventory is allowed. Since each process must run in batch, the schedule for the Mini-Mill consists of grouping and sequencing of lots for each process. However, each process has its own criteria for judging the quality of its lot grouping, which often conflicts with other processes. An efficient scheduling algorithm for the Mini-Mill is proposed. Numerical experiments with real world data suggest that the proposed algorithm yield satisfactory schedules very efficiently. The algorithm is currently used for the actual scheduling of a Mini-Mill in Korea.     

An Evaluation of Tour Scheduling Heuristics with Differences in Employee Productivity and Cost

This study focuses on the manpower tour scheduling problem using data from a lockbox system of a commercial bank. The lockbox system uses employees who differ in productivity, hourly cost, number of available working hours per week, and days-off constraints. These specific problem characteristics require a more general problem formulation and solution procedure for the manpower tour scheduling problem than addressed in previous research. Four heuristic methods for solving the problem (three developed here and a simple round-up procedure) are tested on a set of forty problems. The results of this study show the effort to develop sophisticated heuristic methods for this class of problems is well justified.     

Multi-objective scheduling of two-job families on a single machine

This paper presents a preliminary analysis of the typical scheduling environment in semiconductor manufacturing involving multiple job families, and where more than one objective such as cycle time, machine utilization and the due-date accuracy needs to be simultaneously considered. In this study, the NP-hard problem of scheduling N independent jobs on a single testing machine with due dates and sequence-dependent setup times is addressed, where the multiple objectives are to minimize average cycle time, to minimize average tardiness, and to maximize machine utilization. A Pareto optimal solution, which is not inferior to any other feasible solutions in terms of all objectives, is generated combining the analytically optimal and conjunctive simulated scheduling approach. First, the machine-scheduling problem is modeled using the discrete event simulation approach and the problem is divided into simulation clock based lot selection sub-problems. Then, a Pareto optimal lot is selected using the compromise programming technique for multiobjective optimization at each decision instant in simulated time. With the help of a broad experimental design, this developed solution is then compared with common heuristic-dispatching rules such as SPT and EDD, which show better results for all the objectives over a wide range of problems. The developed scheduling method shows approximately 16.7% reduction in average cycle time, 25.6% reduction in average tardiness, and 21.6% improvement in machine utilization over the common dispatching rules, SPT and EDD.     

A Simulation Study of Sequencing Rules in a Kanban-Controlled Flow Shop*

This paper addresses the problem of sequencing in decentralized kanban-controlled flow shops. The kanban production control system considered uses two card types and a constant withdrawal period. The flow shops are decentralized in the sense that sequencing decisions are made at the local workstation level rather than by a centralized scheduling system. Further, there are no material requirements planning (MRP)-generated due dates available to drive dispatching rules such as earliest due date, slack, and critical ratio. Local sequencing rules suitable for the decentralized kanban production-control environment are proposed and tested in a simulation experiment. These rules are designed so that they can be implemented with only the information available at the workstation level. Example sequencing problems are used to show why the shortest processing time rule minimizes neither average work-in-process inventory nor average finished-goods withdrawal kanban waiting time. Further, it is shown how work station supervisors can use the withdrawal period, in addition to the number of kanbans, to manage work-in-process inventories.     

资源受限下平行工序顺序对优化的0-1规划模型

资源受限是工程项目时刻都可能面对的挑战。由于资源限制,需要将原项目计划中相互之间无优先关系的平行工序调整为顺序工序。平行工序顺序化可导致项目工期延迟,因此需考虑如何使项目工期延迟最小。该平行工序顺序优化问题是项目调度问题,也是排列组合问题,通常难度很大,包括一些NP-hard问题。本文主要研究该问题的一类典型子问题——平行工序顺序对优化,即如何将项目中某2n个平行工序调整为n个顺序工序对,并且对项目工期的影响最小。该问题的总方案数可达到（2n）!/n!。本文借助工序网络（如CPM网络）,运用简单的时间参数量化了平行工序顺序化对项目工期的影响,进而降低问题的求解难度,建立了纯0-1规划模型。实验验证了该模型的求解效率,求解100个平行工序规模的问题平均耗时0.2605秒,而求解500个平行工序规模的问题平均耗时10.66秒。     

Combinatorial Optimization in Real-Time Scheduling: Theory and Algorithms

Real-time computer systems are essential for many applications, such as robot control, avionics, medical instrumentation, manufacturing, etc. The correctness of the system depends on the temporal correctness as well as the functional correctness of the task executions. In order to assure temporal correctness it is necessary that the resources be scheduled to meet the temporal requirements of applications. When we consider the problem of nonpreemptive scheduling of a set of tasks in a processor for which no feasible solution exists, some tasks may have to be rejected so that a schedule can be generated for the rest. In this paper, we consider the problem of generating an optimal schedule such that the number of rejected tasks is minimized, and then the finish time is minimized for the accepted tasks. We propose to use an analytic approach to solve this problem. We first discuss the super sequence based technique which was originally proposed for reducing the search space in testing the feasibility of a task set. Then we show by the Conformation theorem that the super sequence constructed from the task set also provides a valid and reduced search space for the optimization problem. While the complexity of our scheduling algorithm in the worst case remains exponential, our simulation results show that the cost is reasonable for the average case.     

Appointment Scheduling with No‐Shows and Overbooking

We study an overbooking model for scheduling arrivals at a medical facility under no‐show behavior, with patients having different no‐show probabilities and different weights. The scheduler has to assign the patients to time slots in such a way that she minimizes the expected weighted sum of the patients' waiting times and the doctor's idle time and overtime. We first consider the static problem, where the set of patients to be scheduled and their characteristics are known in advance. We partially characterize the optimal schedule and introduce a new sequencing rule that schedules patients according to a single index that is a function of their characteristics. Then we apply our theoretical results and conclusions from numerical experiments to sequential scheduling procedures. We propose a heuristic solution to the sequential scheduling problem, where requests for appointments come in gradually over time and the scheduler has to assign each patient to one of the remaining slots that are available in the schedule for a given day. We find that the no‐show rate and patients' heterogeneity have a significant impact on the optimal schedule and should be taken under consideration.     

Decomposition algorithms for the integrated process planning and scheduling problem

There are several algorithms to solve the integrated process planning and scheduling (IPPS) problem (i.e., flexible job shop scheduling with process plan flexibility) in the literature. All the existing algorithms for IPPS are heuristic-based search methods and no research has investigated the use of exact solution methods for this problem. We develop several decomposition approaches based on the logic-based Benders decomposition (LBBD) algorithm. Our LBBD algorithm allows us to partition the decision variables in the IPPS problem into two models, master-problem and sub-problem. The master-problem determines process plan and operation-machine assignment, while the sub-problem optimizes sequencing and scheduling decisions. To achieve faster convergence, we develop two relaxations for the optimal makespan objective function and incorporate them into the master-problem. We analyze the performance and further enhance the algorithm with two ideas, a Benders optimality cut based on the critical path and a faster heuristic way to solve the sub-problem. 16 standard benchmark instances available in the literature are solved to evaluate and compare the performances of our algorithms with those of the state-of-the-art methods in the literature. The proposed algorithm either results in the optimal solution or improves the best-known solutions in all the existing instances, demonstrating its superiority to the existing state-of-the-art methods in literature.     

A heuristic approach for component scheduling on a high-speed PCB assembly machine

The collect-and-place machine is one of the most widely used placement machines for assembling electronic components on the printed circuit boards (PCBs). Nevertheless, the number of researches concerning the optimisation of the machine performance is very few. This motivates us to study the component scheduling problem for this type of machine with the objective of minimising the total assembly time. The component scheduling problem is an integration of the component sequencing problem, that is, the sequencing of component placements; and the feeder arrangement problem, that is, the assignment of component types to feeders. To solve the component scheduling problem efficiently, a hybrid genetic algorithm is developed in this paper. A numerical example is used to compare the performance of the algorithm with different component grouping approaches and different population sizes.     

Economic Lot Scheduling Problem with Returns

Motivated by a case study of a company that produces car parts, we study the multi‐product economic lot scheduling problem for a hybrid production line with manufacturing of new products and remanufacturing of returned products. For this economic lot scheduling problem with returns (ELSPR), we consider policies with a common cycle time for all products, and with one manufacturing lot and one remanufacturing lot for each product during a cycle. For a given cycle time, the problem is formulated as a mixed integer linear programming (MIP) problem, which provides the basis for an exact solution. The application of this model for one of the core products of the case study company indicates a 16% reduction in cost compared to the current lot scheduling policy.