Analysis of a batch machine fed by an unreliable discrete machine

This paper analyses the behaviour of a manufacturing line consisting of two machines in series where the first machine processes lots one at a time, and is subject to failure and takes a random amount of time to repair when it fails, and the second machine is a perfectly reliable batch machine. A control limit policy is adopted to determine lot sizes for the batch machine. When the batch machine completes processing, if the number of lots in the buffer is greater than or equal to the critical number (Q?), all the lots in the buffer are loaded immediately, otherwise the batch machine waits until Q lots are accumulated. An embedded discrete time Markov-chain approach is proposed, and recursive approaches are developed to derive necessary performance measures. A numerical example explains how to obtain the optimal value of a critical number minimizing the cost functions.     

Single machine scheduling research

This paper reviews static scheduling research on single machine for the last three decades. One hundred seventy one papers were found on this topic after an extensive search in the English language periodicals. These papers are classified on the basis of the objective functions and constraints. Contribution of each paper is analyzed in terms of its theoretical and computational results. An analysis of the literature on the basis of number of articles published in each year, in each category, in different journals and by different authors has also been provided. This reveals several interesting facts about the developments in single machine scheduling (SMS) research and its future.     

On-line machine scheduling with batch setups

We study a class of scheduling problems with batch setups for the online-list and online-time paradigms. Jobs are to be scheduled in batches for processing. All jobs in a batch start and complete together, and a constant setup is prior to each batch. The objective is to minimize the total completion time of all jobs. We primarily consider the special cases of these problems with identical processing times, for which efficient on-line heuristics are proposed and their competitive performance is evaluated.     

Scheduling a single semi-continuous batching machine

This paper addresses a new problem, called semi-continuous batch scheduling, which arises in the heating-operation of tube-billets in the steel industry. Each heating furnace can be regarded as a semi-continuous batching machine, which can handle up to C jobs simultaneously. The jobs in the same batch enter and leave the machine semi-continuously, which differs from the traditional batching machine scheduling where the jobs in same batch have a starting time and a finishing time. In this paper the processing time of a batch depends on the capacity of the semi-continuous batching machine, the longest processing time of jobs in the batch and its size. The objectives are to schedule jobs on the machine so that the makespan and the total completion time are minimized. A schedule for a semi-continuous batching machine consists of a batching and sequencing for the batches. We propose the optimal properties of two different objective functions and present the different dynamic programming algorithms with a running time of O(n²), respectively.     

Discrete parallel machine makespan ScheLoc problem

Scheduling–Location (ScheLoc) problems integrate the separate fields of scheduling and location problems. In ScheLoc problems the objective is to find locations for the machines and a schedule for each machine subject to some production and location constraints such that some scheduling objective is minimized. In this paper we consider the discrete parallel machine makespan ScheLoc problem where the set of possible machine locations is discrete and a set of n jobs has to be taken to the machines and processed such that the makespan is minimized. Since the separate location and scheduling problem are both \(\mathcal {NP}\)-hard, so is the corresponding ScheLoc problem. Therefore, we propose an integer programming formulation and different versions of clustering heuristics, where jobs are split into clusters and each cluster is assigned to one of the possible machine locations. Since the IP formulation can only be solved for small scale instances we propose several lower bounds to measure the quality of the clustering heuristics. Extensive computational tests show the efficiency of the heuristics.     

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.     

Single machine scheduling problems with subcontracting options

In this paper, we study a scheduling model as follows: there are n jobs which can be processed in house on a single machine or subcontracted to a subcontractor. If a job is subcontracted, its processing cost is different from the in-house cost and its delivery lead time is a stepwise function of the total processing time of outsourced jobs. Two objective functions are studied (1) to minimize the weighted sum of the maximal completion time and the total processing cost and (2) to minimize the weighted sum of the number of tardy jobs and the total processing cost. For the first problem, we prove that it is NP-hard and get a pseudo-polynomial time algorithm. For the second problem, we prove that it is NP-hard and get a pseudo-polynomial time algorithm for a special case.     

Scheduling with machine cost and rejection

In this paper we consider the scheduling problem with machine cost and rejection penalties. For this problem, we are given a sequence of independent jobs, each being characterized by its processing time (size) and its penalty. No machine is initially provided, and when a job is revealed the algorithm has the option to purchase new machines. Right when a new job arrives, we have the following choices: (i) reject it, in which case we pay its penalty; (ii) non-preemptively process it on an existing machine, which contributes to the machine load; (iii) purchase a new machine, and assign it to this machine. The objective is to minimize the sum of the makespan, the cost for purchasing machines, and the total penalty of all rejected jobs. For the small job case, (where all jobs have sizes no greater than the cost for purchasing one machine, and which is the generalization of the Ski-Rental Problem) we present an optimal online algorithm with a competitive ratio of 2.     

Solution of a single stage machine load planning problem

A subgradient algorithm and a binary integer assignment algorithm are used in tandem to determine economic run quantities for an injection molding facility. The model considers machine regular time and overtime capability, machine-tool compatibility, storage area capacity, and the economics of lot size decisions. Use of the model in scheduling and alternative facility evaluation are discussed.     

Scheduling of unrelated parallel machines when machine availability is specified

Scheduling problems typically assume uninterrupted availability of machines such that jobs can be processed at any time during this uninterrupted period. However, this assumption is seldom valid in reality. For a variety of reasons, e.g. machine adjustments, shift changes, planned maintenance, etc. machines are available only at specified times. The duration for which the machine is not available is known as the vacation. This paper considers the problem of scheduling jobs on unrelated parallel machines when machine vacations are specified. Two cases are considered, first, when the machine vacations are known apriori, and the second, when these constraints are not known apriori. Algorithms have been developed for both models, and computational results are also reported.     

一类新型批处理机调度问题的理论分析

钢卷在冷轧生产中,为了改进其性能,需要在罩式炉进行退火,退火过程由加热、保温和降温三段组成,而这三段处理时间由于工艺上的要求不能归结为一个时间,这与传统批处理机调度有明显的差别.对新型批处理机的总加权完成时间最小化问题建立了非线性整数规划模型,开发了基于动态规划的启发式算法.通过理论分析,获得该算法的误差性能比为3.对于三段中的某一段板卷的处理时间相同的情况,证明了启发式算法的误差性能比是2,而且证明是紧界.对于三段中的某二段板卷的处理时间相同的情况,证明了启发式算法是最优算法.对启发式算法扩展到带有任意段的加工时间的一般情况进行了性能分析.     

Value-at-risk support vector machine: stability to outliers

A support vector machine (SVM) stable to data outliers is proposed in three closely related formulations, and relationships between those formulations are established. The SVM is based on the value-at-risk (VaR) measure, which discards a specified percentage of data viewed as outliers (extreme samples), and is referred to as \(\mathrm{VaR}\) -SVM. Computational experiments show that compared to the \(\nu \) -SVM, the VaR-SVM has a superior out-of-sample performance on datasets with outliers.     

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.     

The queuing theory machine interference model: use and application

This paper aims at making the queuing theory machine interference model a usable tool for process designers, production managers, and others who face decisions regarding the number of machines and the size of crew to operate/maintain them. The model is presented conceptually and compared with other existing models. Next, the model is analysed, and parameter calculations are detailed: a ready-to-implement procedure is given to carry out these calculations. Finally, the use of the model and its application in the work-study context are illustrated by examples.     

Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence

In this paper, we introduce the concept of “workload fence" into online machine rental and machine scheduling problems. With the knowledge of workload fence, online algorithms acquire the information of a finite number of first released jobs in advance. The concept originates from the frozen time fence in the domain of master scheduling in materials management. The total processing time of the jobs foreseen, corresponding to a finite number of jobs, is called workload fence, which is irrelevant to the job sequence. The remaining jobs in the sequence, however, can only become known on their arrival. This work aims to reveal whether the knowledge of workload fence helps to boost the competitive performance of deterministic online algorithms. For the online machine rental problem, we prove that the competitiveness of online algorithms can be improved with a sufficiently large workload fence. We further propose a best online algorithm for the corresponding scenario. For online parallel machine scheduling with workload fence, we give a positive answer to the above question for the case where the workload fence is equal to the length of the longest job. We also show that the competitiveness of online algorithms may not be improved even with a workload fence strictly larger than the largest length of a job. The results help one manager to make a better decision regarding the tradeoff between the performance improvement of online algorithms and the cost caused to acquire the knowledge of workload fence.

     

A game mechanism for single machine sequencing with zero risk

A problem is studied in which several non-cooperating clients compete for earlier execution of their jobs in a processing sequence of a single service provider in order to minimize job completion time costs. The clients can move their jobs earlier in a given sequence. They are assumed not to take a risky decision that can decrease their utility function. A game mechanism is suggested such that each client has no incentive to claim false cost and a social criterion is addressed, which is the minimum total cost of all clients. Algorithmic aspects of this mechanism are analyzed such as relations between the values of game equilibria and the social optimum, the computational complexity of finding a game equilibrium and the values of the price of anarchy and the price of stability.     

Single machine scheduling: A comparison of two solution procedures

Recent research on the single machine scheduling problem has focused on the treatment of multiple scheduling objectives. Most works have used some combination of mean flowtime, maximum tardiness, or total tardiness as scheduling criteria. Previous research has largely ignored earliness as a scheduling criterion. This paper presents a model that employs the criteria of flowtime as a measure of work-in-process (WIP) inventory and total job earliness to represent finished goods inventory. Total tardiness is used to represent customer satisfaction. The three criteria are used to form a single, weighted-sum objective function for guiding the choice of the best processing sequence. Two procedures are presented that might be used to solve this problem. The first is an enumeration scheme using bounding and dominance criteria that have been developed to aid efficient solution, and the second is a mixed integer linear programming (LP) formulation. Computational experience with the two models is also presented.     

Centerline-SMED integration for machine changeovers improvement in food industry

This paper demonstrates how it is possible to combine SMED with Centerlining in complex production environments with numerous changes of format, product, raw materials and tools. This research proposes a methodology involving an initial application of Centerlining and, once the machinery and the process are stable, the subsequent implementation of SMED. Furthermore, it aims to show that it is possible to achieve improved output and reduced machinery changeover time while ensuring that the effect achieved by SMED is more stable. This increases the organizational advantages with respect to the implementation of SMED without prior application of Centerlining. The most important overall conclusion is that a successful application of SMED must always be accompanied by another type of tool or technique to maximize the results of its application. And, as presented in this work, one technique that enables significant improvements to SMED is the application of Centerlining.