Scheduling tool changes and special jobs on a single machine to minimize makespan

This paper considers a variation of the classical single machine scheduling problem with tool changes. In the variation, two sets of jobs, namely special jobs and normal jobs, are considered. By special jobs, we mean that each special job must be processed within the first prefixed time units of a tool life. To solve the scheduling problem with small size and moderate size, we propose two mathematical programming models. To solve the scheduling problem with large size, we propose three sets of algorithms and focus on the performance of six algorithms based on the studies of a new bin packing problem. Worst-case analysis is conducted. Numerical experiment shows that each of the six algorithms can solve instances with up to 5000 jobs in about 0.5 s with an average relative error less than 4%.     

Single-machine scheduling with production and rejection costs to minimize the maximum earliness

In this paper, we consider the single-machine scheduling problem with production and rejection costs to minimize the maximum earliness. If a job is accepted, then this job must be processed on the machine and a corresponding production cost needs be paid. If the job is rejected, then a corresponding rejection cost has to be paid. The objective is to minimize the sum of the maximum earliness of the accepted jobs, the total production cost of the accepted jobs and the total rejection cost of the rejected jobs. We show that this problem is equivalent to a single-machine scheduling problem to minimize the maximum earliness with two distinct rejection modes. In the latter problem, rejection cost might be negative in the rejection-award mode which is different from the traditional rejection-penalty mode in the previous literatures. We show that both of two problems are NP-hard in the ordinary sense and then provide two pseudo-polynomial-time algorithms to solve them. Finally, we also show that three special cases can be solved in polynomial time.     

Distributionally Robust Optimization of Two‐Stage Lot‐Sizing Problems

This paper studies two‐stage lot‐sizing problems with uncertain demand, where lost sales, backlogging and no backlogging are all considered. To handle the ambiguity in the probability distribution of demand, distributionally robust models are established only based on mean‐covariance information about the distribution. Based on shortest path reformulations of lot‐sizing problems, we prove that robust solutions can be obtained by solving mixed 0‐1 conic quadratic programs (CQPs) with mean‐risk objective functions. An exact parametric optimization method is proposed by further reformulating the mixed 0‐1 CQPs as single‐parameter quadratic shortest path problems. Rather than enumerating all potential values of the parameter, which may be the super‐polynomial in the number of decision variables, we propose a branch‐and‐bound‐based interval search method to find the optimal parameter value. Polynomial time algorithms for parametric subproblems with both uncorrelated and partially correlated demand distributions are proposed. Computational results show that the proposed models greatly reduce the system cost variation at the cost of a relative smaller increase in expected system cost, and the proposed parametric optimization method is much more efficient than the CPLEX solver.     

Economic Production Lot Sizing with Periodic Costs and Overtime*

Traditional approaches for modeling economic production lot‐sizing problems assume that a single, fixed equipment setup cost is incurred each time a product is run, regardless of the quantity manufactured. This permits multiple days of production from one production setup. In this paper, we extend the model to consider additional fixed charges, such as cleanup or inspection costs, that are associated with each time period's production. This manufacturing cost structure is common in the food, chemical, and pharmaceutical industries, where process equipment must be sanitized between item changeovers and at the end of each day's production. We propose two mathematical problem formulations and optimization algorithms. The models' unique features include regular time production constraints, a fixed charge for each time period's production, and the availability of overtime production capacity. Experimental results indicate the conditions under which our algorithms' performance is superior to traditional approaches. We also test the procedures on a set of lot‐sizing problems facing a national food processor and document their potential economic benefit.     

2-Distance vertex-distinguishing index of subcubic graphs

This paper addresses the performance of scheduling algorithms for a two-stage no-wait hybrid flowshop environment with inter-stage flexibility, where there exist several parallel machines at each stage. Each job, composed of two operations, must be processed from start to completion without any interruption either on or between the two stages. For each job, the total processing time of its two operations is fixed, and the stage-1 operation is divided into two sub-parts: an obligatory part and an optional part (which is to be determined by a solution), with a constraint that no optional part of a job can be processed in parallel with an idleness of any stage-2 machine. The objective is to minimize the makespan. We prove that even for the special case with only one machine at each stage, this problem is strongly NP-hard. For the case with one machine at stage 1 and m machines at stage 2, we propose two polynomial time approximation algorithms with worst case ratio of \(3-\frac{2}{m+1}\) and \(2-\frac{1}{m+1}\), respectively. For the case with m machines at stage 1 and one machine at stage 2, we propose a polynomial time approximation algorithm with worst case ratio of 2. We also prove that all the worst case ratios are tight.     

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.     

A note on special optimal batching structures to minimize total weighted completion time

A batch is a subset of jobs which must be processed jointly in either serial or parallel form. The algorithmic aspects of the batching scheduling problems have been extensively studied in the literature. This paper presents necessary and sufficient conditions of the existence of optimal batch sequences for the single machine, batching, total weighted completion time scheduling problems on two batching ways: (1) all jobs form one batch; (2) each batch contains a single job. This kind of conditions can help us to recognize some special optimal schedules quickly. Research supported by NSFC (10671183).     

Real-time scheduling and control of one-of-a kind production

Due to the great diversity of product types in one-of-a-kind production (OKP), the production scheduling and control in OKP is much more difficult than production scheduling and control of other production systems, e.g. mass production and batch production. Hence, the production efficiency in OKP companies is relatively lower. To improve productivity in OKP, a dynamic hierarchy production control system is presented. Using this control structure, a production system in an OKP company can be flexibly organized or re-organized according to the structure of a customized product (or an OKP product). Production synchronizing and scheduling algorithms for OKP shop floor production control are presented. Using these algorithms, a cybernetic model can be developed for shop floor control in OKP. The algorithms are applied to two alternate production scheduling goals in OKP, namely ASAP (as soon as possible) production and JIT (just in time) production.     

Scheduling two job families on a single machine with two competitive agents

We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a single machine. A setup time is needed for a job if it is the first job to be processed on the machine or its processing on the machine follows a job that belongs to another family. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The aim is to find a schedule for all the jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent being bounded by a fixed value \(Q\). Polynomial-time and pseudo-polynomial-time algorithms are designed to solve the problem involving various combinations of regular scheduling objective functions.     

Heuristic algorithms for the two-machine flowshop with limited machine availability

The paper studies a flowshop scheduling problem where machines are not available in given time intervals. The objective is to minimize the makespan. The problem is known to be NP-hard for two machines. We analyze constructive and local search based heuristic algorithms for the two-machine case. The algorithms are tested on easy and difficult test problems with up to 100 jobs and 10 intervals of non-availability. Computational results show that the algorithms perform well. For many problems an optimum solution is found.     

Single process plan scheduling with genetic algorithms

AIn this paper, a genetic algorithm model for scheduling manufacturing resources is developed for the case when there is only one process plan available per job, hence there is no routeing flexibility. The scheduling objectives considered are minimizing the makespan and mean flow time. Genetic algorithms design issues are discussed and the working of the employed genetic operators is explained in detail. Parameters for the genetic algorithms used for single process plan scheduling SPPS problems are set through extensive experimentation. Finally, the genetic algorithms approach is compared with several other approaches in terms of optimality of solution and computAuthors: ing time. It was observed that in most cases the genetic algorithms approach performed better than other approaches both in terms of finding an optimal or near optimal solution as well as computing time.     

The Critical Few Minutes in Scheduling Time‐Varying Queuing Systems

For nonstationary queuing systems where demand varies over time, an important practical issue is scheduling the number of servers to be available at various times of the day. Widely used scheduling procedures typically involve adding servers at natural time points (e.g., on the hour or at half past the hour) during peak demand periods. Scheduling is often complicated by restrictions on the minimum amount of time (human) servers must work, the earliest (or latest) time a server is available, and limits on the maximum number of servers that can be used at any one time. This paper was motivated by experience with actual queuing systems that embodied such complications. For these systems common scheduling methods that used “natural” starting times for servers resulted in needlessly long customer waits. This research demonstrates that changing the starting times of servers by only a few minutes can have dramatic impacts on customer waiting times for extended periods. In addition, the results highlight the importance of server punctuality.     

A bicriteria approach to scheduling a single machine with job rejection and positional penalties

Single machine scheduling problems have been extensively studied in the literature under the assumption that all jobs have to be processed. However, in many practical cases, one may wish to reject the processing of some jobs in the shop, which results in a rejection cost. A solution for a scheduling problem with rejection is given by partitioning the jobs into a set of accepted and a set of rejected jobs, and by scheduling the set of accepted jobs among the machines. The quality of a solution is measured by two criteria: a scheduling criterion, F1, which is dependent on the completion times of the accepted jobs, and the total rejection cost, F2. Problems of scheduling with rejection have been previously studied, but usually within a narrow framework—focusing on one scheduling criterion at a time. This paper provides a robust unified bicriteria analysis of a large set of single machine problems sharing a common property, namely, all problems can be represented by or reduced to a scheduling problem with a scheduling criterion which includes positional penalties. Among these problems are the minimization of the makespan, the sum of completion times, the sum and variation of completion times, and the total earliness plus tardiness costs where the due dates are assignable. Four different problem variations for dealing with the two criteria are studied. The variation of minimizing F1+F2 is shown to be solvable in polynomial time, while all other three variations are shown to be $\mathcal{NP}$ -hard. For those hard problems we provide a pseudo polynomial time algorithm. An FPTAS for obtaining an approximate efficient schedule is provided as well. In addition, we present some interesting special cases which are solvable in polynomial time.     

Scheduling in an assembly-type production chain with batch transfer

This paper addresses a three-machine assembly-type flowshop scheduling problem, which frequently arises from manufacturing process management as well as from supply chain management. Machines one and two are arranged in parallel for producing component parts individually, and machine three is an assembly line arranged as the second stage of a flowshop for processing the component parts in batches. Whenever a batch is formed on the second-stage machine, a constant setup time is required. The objective is to minimize the makespan. In this study we establish the strong NP-hardness of the problem for the case where all the jobs have the same processing time on the second-stage machine. We then explore a useful property, based upon which a special case can be optimally solved in polynomial time. We also study several heuristic algorithms to generate quality approximate solutions for the general problem. Computational experiments are conducted to evaluate the effectiveness of the algorithms.     

Lot sizing in workload control systems

An important basis for workload control (WLC) is the existence of functional relationships between the mean level of work-in-process (WIP) and the values of important goal variables, like average flow time, capacity utilization, etc. These functional relationships are largely influenced by the lot sizes. This means that the usual objective of lot sizing must be supplemented by considering the impact of lot sizes on the relationships between WIP and the other goal variables. Here it is shown that this insight leads to flow time oriented lot sizing models. This type of lot sizing models is analysed. It is argued that the derivation of simple rules for lot sizing is an important research topic, and a model for deriving such rules is presented. Some rules are derived from the model, assuming that the batches are processed by an M/G/1 server, and it is shown that these rules support insights based on simulation in the 1980s. Topics for future research are outlined as well.     

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.     

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.     

Intelligent scheduling model and algorithm for manufacturing

This paper puts forward an intelligent scheduling model based on Hopfield neural network and a unified algorithm for manufacturing. The energy computation function and its dynamic state equation are derived and discussed in detail about their coefficients (parameters) and steps (Delta t) in iteration towards convergence. The unified model is focused on the structure of the above function and equation, in which the goal and penalty items must be involved and meet different schedule models. The applications to different schedule mode including jobshop static scheduling, scheduling with due-date constraint or priority constraint, dynamic scheduling, and JIT (just in time) scheduling are discussed, and a series of examples with Gantt charts are illustrated.     

ON THE DESIGN OF HIERARCHICAL PRODUCTION PLANNING SYSTEMS

To provide effective managerial support for decisions related to production planning and scheduling processes, it is useful to partition the set of decisions into a hierarchical framework. In the resulting system, higher level decisions impose constraints on lower level actions, and lower level decisions provide the necessary feed-back to reevaluate higher level actions. The purpose of this paper is to suggest optimum procedures to deal with the resulting subproblems and to analyze the interaction mechanisms among the different hierarchical levels. Computational results are given.     

Scheduling with interjob communication on parallel processors

Consider a scheduling problem in which a set of tasks needs to be scheduled on m parallel processors. Each task \(T_i\) consists of a set of jobs with interjob communication demands, represented by a weighted, undirected graph \(G_i\). The processors are assumed to be interconnected by a shared communication channel, which can be used by jobs to communicate among each other while being processed in parallel. In each time step, the scheduler assigns jobs to the processors and allows any processed job to use a certain capacity of the channel in order to satisfy (parts of) its communication demands to adjacent jobs processed in the same step. The goal is to find a schedule with minimum length in which the communication demands of all jobs are satisfied. We show that this problem is NP-hard in the strong sense even if the number of processors is constant and the underlying graph is a single path or a forest with arbitrary constant maximum degree. Consequently, we design and analyze approximation algorithms with asymptotic approximation ratio \(\min \{1.8, 1.5 \frac{m}{m-1}\}+1\) if the underlying graph G, the union of the \(G_i\), is a forest. For general graphs it is \(\min \left\{ 1.8, \frac{1.5m}{m-1}\right\} \cdot \left( \text {arb}(G) + \frac{5}{3}\right) \), where \(\text {arb}(G)\) denotes the arboricity of G.