Optimal allocation and processing time decisions on non-identical parallel CNC machines: epsilon-constraint approach

Date

2007-12-01

Author

Gürel, Sinan

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

192
views

0
downloads

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. In this paper, we deal with making optimal machine-job assignments and processing time decisions so as to minimize total manufacturing cost while the makespan being upper bounded by a known value, denoted as E-constraint approach for a bicriteria problem. We then give optimality properties for the resulting single criterion problem. We provide alternative methods to compute cost lower bounds for partial schedules, which are used in developing an exact (branch and bound) algorithm. For the cases where the exact algorithm is not efficient in terms of computation time, we present a recovering beam search algorithm equipped with an improvement search procedure. In order to find improving search directions, the improvement search algorithm uses the proposed cost bounding properties. Computational results show that our lower bounding methods in branch and bound algorithm achieve a significant reduction in the search tree size that we need to traverse. Also, our recovering beam search and improvement search heuristics achieve solutions within 1% of the optimum on the average while they spent much less computational effort than the exact algorithm.

Subject Keywords

Management Science and Operations Research, Modelling and Simulation, Information Systems and Management

URI

https://hdl.handle.net/11511/36210

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

DOI

https://doi.org/10.1016/j.ejor.2006.10.024

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Scheduling parallel CNC machines with time/cost trade-off considerations Gürel, Sinan (Elsevier BV, 2007-09-01) When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well-known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. We also know that scheduling decisions are quite sensitive to the processing times. Therefore, this paper considers minimizing total manufacturing cos...
Considering manufacturing cost and scheduling performance on a CNC turning machine Gürel, Sinan (Elsevier BV, 2007-02-16) A well known industry application that allows controllable processing times is the manufacturing operations on CNC machines. For each turning operation as an example, there is a nonlinear relationship between the manufacturing cost and its required processing time on a CNC turning machine. If we consider total manufacturing cost (F-1) and total weighted completion time (F-2) objectives simultaneously on a single CNC machine, making appropriate processing time decisions is as critical as making job sequencin...
SCHEDULING UNDER A NONRENEWABLE RESOURCE CONSTRAINT TOKER, A; KONDAKCI, S; ERKIP, N (Informa UK Limited, 1991-09-01) This paper examines a single-machine, non-renewable-resource-constrained scheduling problem where jobs have arbitary processing times and resource requirements. Unit supply of a resource is assumed at each time period. Performance criterion is makespan. It is proved that this problem is identical to the two-machine flowshop problem, enabling the use of Johnson's algorithm. Immediate extensions of this result are presented.
Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria Ozlen, M.; Azizoğlu, Meral (Informa UK Limited, 2011-01-01) In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the follo...
Operational fixed job scheduling problem under spread time constraints: a branch-and-price algorithm Solyali, O.; Ozpeynirci, O. (Informa UK Limited, 2009-01-01) This study addresses the operational fixed job scheduling problem under spread time constraints. The problem is to select a subset of jobs having fixed ready times and deadlines for processing on identical parallel machines such that total weight of the selected jobs is maximised. We first give a mathematical formulation of the problem and then reformulate it using Dantzig-Wolfe decomposition. We propose a branch-and-price algorithm that works on the reformulation of the problem. Computational results show ...

Citation Formats

S. Gürel, “Optimal allocation and processing time decisions on non-identical parallel CNC machines: epsilon-constraint approach,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, pp. 591–607, 2007, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/36210.