Note on scheduling with general learning curves to minimize the number of tardy jobs

Several research studies have confirmed that people and organizations become better at their tasks as the tasks are repeated. The effect of this learning phenomenon on classical scheduling problems has been studied recently. One of the single-machine scheduling problems which seems to become nontrivial when learning effects are introduced is that of minimizing the number of tardy jobs. In this note, we study the special case where all jobs share a common due-date. We show that even when the learning process is assumed to be general and job-dependent, the problem remains polynomially solvable.     

Optimal scheduling of batch industrial facilities

An increasing interest in batch processing has been evident in recent years. This renewed interest is explained by the inherent flexibility of such plants that permits a high level of response to uncertain market conditions and requirements. This level of response does require the use of efficient tools to help the decision-making process at the design and operational level. This paper presents a Mixed Integer Linear Program (MILP) model to optimise the scheduling of batch facilities subject to changeovers and distribution constraints so as to guarantee a pre-defined objective. Such an objective can be defined as the minimum orders' total lateness or the maximum distribution units loading capacity, among others. A continuous-time representation is used as well as the concept of job predecessor and successor to effectively handle changeovers. Facilities having non-identical parallel units/lines, sequence-dependent orders, finite release times for units and orders, restrictions on the suitability of jobs to lines/units and different possible destinations to available distribution units are also considered. Based on these characteristics the proposed model is able to determine the optimal allocation of jobs to production lines/units, the sequence of jobs on every line/unit and the starting and completion production times of each order. Also, the usage and allocation of the distribution resources (eg trucks) to orders and destinations are obtained based on their availability and suitability to the orders. The model led to the development of a prototype information system that can be used as a tool to help the decision-making process at the operational plant level.Finally, the applicability of the proposed system/formulation is shown through the resolution of an industrial real case where the production of polymers is performed.     

Operational Research and Management

The purpose of this paper is to discuss and if possible to dispel the industrialist's misunderstanding of operational research. The author lists some of the varied ideas held by industrialists of operational research including several which are contradictory, as for example (a) That operational research is new and revolutionary; and (b) That operational research proves nothing new and has always been practised without being so named.A number of suggestions are then made and developed, which should lead to a better understanding. These include, clearer definitions of operational research and a better adaptation of the specialized literature to the needs of industrial management, with particular emphasis on the publication of real rather than synthetic case histories. Headings of sections are:

1. 1
   The attitude of industrialists.
    
2. 2
   The exact nature of operational research.
    
3. 3
   Problems, criteria, models.
    
4. 4
   The practice of operational research in business.
    

     

Flow-based formulations for operational fixed interval scheduling problems with random delays

We deal with operational fixed interval scheduling problem with random delays in job processing times. We formulate two stochastic programming problems. In the first problem with a probabilistic objective, all jobs are processed on available machines and the goal is to obtain a schedule with the highest attainable reliability. The second problem is to select a subset of jobs with the highest reward under a chance constraint ensuring feasibility of the schedule with a prescribed probability. We assume that the multivariate distribution of delays follows an Archimedean copula, whereas there are no restrictions on marginal distributions. We introduce new deterministic integer linear reformulations based on flow problems. We compare the formulations with the extended robust coloring problem, which was shown to be a deterministic equivalent to the stochastic programming problem with probabilistic objective by Branda et al. (Comput Ind Eng 93:45–54, 2016). In the numerical study, we report average computational times necessary to solve a large number of simulated instances. It turns out that the new flow-based formulation helps to solve the FIS problems considerably faster than the other one.     

Lessons for O.R. from A.I.: A Scheduling Case Study

This paper compares operational research (O.R.) with the currently fashionable topic of artificial intelligence (A.I.) at a detailed level. A.I. concepts, techniques and history are summarized, and O.R. and A.I. approaches compared. A case study-the development of a potential aid to scheduling repair jobs on RAF squadrons—is described. The paper shows where A.I. concepts and techniques were used in the prototype program, known as the Fault Identification & Expediting Repair (FIXER) system. Finally, some lessons for O.R. are drawn.     

The Evaluation of Possible Alternative Forging Techniques

This paper describes the early stages of a long-term operational research project which is concerned with increasing the efficiency of the forging industry. The aims of the work have been to provide a yardstick by which individual forges can judge their own efficiency; to provide information which will indicate which lines to follow to effect improvements; to assess the likely effects of current research; and to evaluate possible future lines of research.The first two aims have been satisfied by comparative studies, and the second two by a process of "breakdown and synthesis". A characteristic of operational research in a field such as this, is the need to acquire an understanding of the technology of the processes involved.     

A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines

We study the problem of scheduling n non-preemptive jobs on m unrelated parallel machines. Each machine can process a specified subset of the jobs. If a job is assigned to a machine, then it occupies a specified time interval on the machine. Each assignment of a job to a machine yields a value. The objective is to find a subset of the jobs and their feasible assignments to the machines such that the total value is maximized. The problem is NP-hard in the strong sense. We reduce the problem to finding a maximum weight clique in a graph and survey available solution methods. Furthermore, based on the peculiar properties of graphs, we propose an exact solution algorithm and five heuristics. We conduct computer experiments to assess the performance of our and other existing heuristics. The computational results show that our heuristics outperform the existing heuristics.     

Asymptotic optimality of statistical multiplexing in pipelined processing

The throughput of pipelined processing ofheterogeneous multitasked jobs is computed and optimized in this study. There areK job classes. Each job hasM tasks which have to be processed in a given order (same for all tasks) on a pipeline ofM processors. Tasks have random processing times. The jobs of each class form a stationary and ergodic sequence (with respect to their task processing times). Classes are differentiated by distinct statistics and may not be jointly stationary or ergodic. Thus, the jobs are overall statistically heterogeneous. We are interested in the average execution time per job , when the job populations of the various classes become very large (asymptotically). This is shown to depend on the order in which jobs enter the pipeline. Under the natural class-based ordering, where all jobs of the first class enter first, followed by those of the second, third, and so on, the quantity is computed, but is shownnot to attain its minimal value in general. On the contrary, appropriate statistical multiplexing of jobs of different classes on the pipeline is shown to minimize the average execution time per job on every sample path (with probability one). The procedure, calledbalanced statistical multiplexing, is constructed and the minimal is computed in terms of the average execution times of the job tasks.     

Operational Research for “Multi-organizations”

The need for operational research in the public and social services draws attention to the problems of conflicting and competing objectives present in such situations. The characteristics of a "multi-organization" are described, it consists of parts of several organizations, which come together for some task. Examples are given of the problems of doing operational research in multi-organizations and some possible approaches and models are suggested. Aspects of operational research methodology which require further development are indicated.     

Dynamic Programming State-Space Relaxation for Single-Machine Scheduling

The problem of sequencing jobs on a single machine to minimize total cost is considered. Machine capacity constraints require that, at any time, at most one job is processed. Also, no machine idle-time between processing jobs is allowed. In contrast to most research, it is not assumed that the cost is a non-decreasing function of completion time. A dynamic programming formulation of the problem is presented. Since the number of states required by this formulation is prohibitively large, the possibilities for branch and bound algorithms are explored. It is shown that the dynamic programming formulation can be relaxed by mapping the state-space onto a smaller state-space and performing the recursion on this smaller state-space, thereby giving a lower bound. Techniques for improving this lower bound through the use of penalties and through the use of state-space modifiers are discussed. Computational results are presented for the problem in which each job has a due date, and the objective is to minimize the sum of holding costs for jobs completed before their due date and tardiness costs for jobs completed after their due date.     

Profile of Current Members of the Operational Research Society

The study described here was based on a questionnaire survey in the summer of 1967 of all the then members of the Operational Research Society. It concerns factual data about Operational Research Society members relating to their general background, the area of operational research and the industry they are engaged in, age and salary, undergraduate and postgraduate education, training in operational research, time spent in operational research and in industry prior to operational research. It examines the relationships between these aspects of their background and looks for trends which may indicate how the nature of the men entering the profession may be changing.     

Scheduling for a multifunction phased array radar system

A multifunction radar is a new, complex, radar system which combines the previously isolated tasks of searching volumes of space, tracking targets and guiding missiles. This study was instigated by the Defence Research Agency who require scheduling rules for their newly developed multifunction radar system. The primary interest when looking at the operational efficiency of this type of radar system is to schedule the radar jobs effectively. These jobs take the form of a coupled task which consists of two distinct operations that require processing in a predetermined order and at a specified interval apart. In the radar scenario, each job is cyclic in nature with its own due date and processing time. The need for an on-line scheduler restricts the radar controller to use heuristic methods. A detailed functional simulation model, which generates a multifunction radar environment, has been developed to aid the evaluation of the various scheduling heuristics that we have proposed.     

Single machine scheduling with common due date assignment in a group technology environment

We consider a scheduling problem in which n jobs are grouped into F groups and are to be processed on a single machine. A machine setup time is required when the machine switches from one group of jobs to the other. All jobs have a common due date that needs to be determined. The objective is to find an optimal common due date and an optimal sequence of jobs to minimize the sum of the cost of tardy jobs and the cost related to the common due date. We consider two cases:

• 1.(i) the jobs have to be processed in groups; and
• 2.(ii) the jobs do not have to be processed in groups.

Analytical results are presented and computational algorithms are developed.     

Teaching Operational Research Technique

Good technique, i.e. competence in carrying out operational research, is as vital for the practitioner to acquire as competence in the traditional ‘techniques’. It is suggested that universities should teach students how to conduct simple projects prior to alerting them to more sophisticated methodological issues.As an aid to this task, the traditional five or six parts of an operational research project are broken down and extended into 39 steps, and regrouped into three phases. Also, five skills are identified as being conceptually essential to "good" operational research, which students can develop through tackling suitable case studies.     

Single-machine scheduling to minimize earliness and number of tardy jobs

This paper considers the problem of assigning a common due-date to a set of simultaneously available jobs and sequencing them on a single machine. The objective is to determine the optimal combination of the common due-date and job sequence that minimizes a cost function based on the assigned due-date, job earliness values, and number of tardy jobs. It is shown that the optimal due-date coincides with one of the job completion times. Conditions are derived to determine the optimal number of nontardy jobs. It is also shown that the optimal job sequence is one in which the nontardy jobs are arranged in nonincreasing order of processing times. An efficient algorithm of O(n logn) time complexity to find the optimal solution is presented and an illustrative example is provided. Finally, several extensions of the model are discussed.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG0036424. The authors are thankful to two anonymous referees for their constructive comments.     

Operational Research and Corporate Planning in Railway Management

The current corporate planning process in Westrail is described and the roles played by operational research and mathematical modelling identified. They do not include forecasting the future. Instead of the "predict and prepare paradigm" a planning approach that tries to design the future has been adopted. The organisation is described in terms of how it has evolved, what it now is, and the key features of its environment. The three stages of planning are described-strategic, tactical and operational. These provide the means for management control of the railway. Environmental assessments linked to goal setting activities are incorporated within the planning process. The significance of operational research in planning, in particular mathematical modelling, is also described. Instead of finding problems to which existing techniques can be applied, O.R. is used to provide effective operational and planning systems as a means of assisting management to design the future for the organisation.     

Operational Research and the Universities

University staff may contribute to operational research by developing and refining its special techniques, or by becoming involved in operational research projects; they may investigate practice to guide them in their research, or in the training of operation analysts. The universities are, in many ways, ideally equipped for operational research work, but involvement in long-term consulting activities is not without serious problems of its own.     

Two-machine flowshop scheduling to minimize the number of tardy jobs

We consider the two-machine flowshop problem with the objective of minimizing the total number of tardy jobs. Since this problem is known to be strongly NP-hard, algorithms are described for four polynomially solvable special cases. In addition, several heuristic algorithms are developed to find optimal or near optimal schedules. Results of computational tests in solving problems up to 60 jobs are reported and directions for future research are provided.     

Flowshop scheduling problem to minimize total completion time with random and bounded processing times

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.